C++ 编程练习题 – 左子树叶节点之和 (深度优先+广度优先+递归)

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
        if (root == NULL) return 0;
        queue< pair<TreeNode*, bool> > q;
        q.push(make_pair(root, false));
        auto r = 0;
        while (!q.empty()) {
            auto p = q.front();
            q.pop();
            if (p.first->left == NULL && p.first->right == NULL && p.second) {
                r += p.first->val;  // sum the value if it comes from left
            }
            if (p.first->left) {
                q.push(make_pair(p.first->left, true));                
            }
            if (p.first->right) {
                q.push(make_pair(p.first->right, false));
            }
        }
        return r;        
    }
};

class Solution {
public:
    void walk(TreeNode* root, bool left) {
        if (root == NULL) return;
        // leaf
        if (root->left == NULL && root->right == NULL) {
            if (left) { // sum only left branches
                sum += root->val;
            }
        }
        if (root->left != NULL) { // DFS left sub tree
            walk(root->left, true);
        }
        if (root->right != NULL) { // DFS right sub tree
            walk(root->right, false);
        }
    }
    int sumOfLeftLeaves(TreeNode* root) {
        if (root) {
            walk(root->left, true);
            walk(root->right, false);
        }
        return sum;
    }
private:
    int sum = 0;
};