链表与树相关的题。

1290. Convert Binary Number in a Linked List to Integer

Analysis

按照链表结点的值，计算出其表示的二进制数。

Code

method 1

很自然的就会想到这样的迭代做法：

class Solution {
public:
    int getDecimalValue(ListNode* head) {
        ListNode *p = head;
        int ret = 0, cnt = 0;
        while(p) {
            cnt++;
            p = p->next;
        }
        p = head;
        cnt--;
        while(p) {
            if(p->val) ret += (1 << cnt);
            cnt--;
            p = p->next;
        }
        return ret;
    }
};

method 2

实际上，并不是一定非要求出链表的结点数，只需要每次计算前，先乘以 2，再相加即可。

class Solution {
public:
    int getDecimalValue(ListNode* head) {
        ListNode *p = head;
        int ret = 0;
        while(p) {
            ret <<= 1;
            ret |= p->val;
            p = p->next;
        }
        return ret;
    }
};

876. Middle of the Linked List

这个题是做过的题，参考：Leetcode_14 天算法入门_day5。

104. Maximum Depth of Binary Tree

这个题也是做过的题，参考：Leetcode_14 天数据结构入门_day11。

404. Sum of Left Leaves

Analysis

求所有左边叶子结点之和。

Code

dfs

使用 dfs 的难点在于到达叶子结点的时候，无法判断此结点是否是左叶子，所以需要提前判断。

class Solution {
public:
    bool isleaf(TreeNode *node) {
        return !node->left && !node->right;
    }
    int dfs(TreeNode *root) {
        int ans = 0;
        if(root->left) ans += isleaf(root->left) ? root->left->val : dfs(root->left);
        if(root->right && !isleaf(root->right)) ans += dfs(root->right);
        return ans;
    }
    int sumOfLeftLeaves(TreeNode* root) {
        if(!root) return 0;
        else return dfs(root);
    }
};

也可以写的更简略一点：

class Solution {
public:
    bool isleaf(TreeNode *node) {
        return node && !node->left && !node->right;
    }
    int sumOfLeftLeaves(TreeNode* root) {
        if(!root) return 0;
        return sumOfLeftLeaves(root->left) + sumOfLeftLeaves(root->right) + (isleaf(root->left) ? root->left->val : 0);
    }
};

bfs

bfs 的思路感觉要清晰很多。

class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
        int sum = 0;
        if(!root) return sum;
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()) {
            TreeNode *node = q.front(); q.pop();
            if(node->left) {
                if(!node->left->left && !node->left->right) sum += node->left->val;
                else q.push(node->left);
            }
            if(node->right) q.push(node->right);
        }
        return sum;
    }
};

Summary

树的递归还是不熟练啊...还得多练习一下。