404. 左叶子之和

原题链接：404. 左叶子之和

思路：
首先要注意是判断左叶子，不是二叉树左侧节点，所以不要上来想着层序遍历。如果是层序遍历的话肯定是错的
判断条件，结点的左孩子不为空，且左孩子结点的左右孩子结点都为空 该结点为左侧的叶子结点
接下来只需要将左侧的叶子结点累加起来就行了

全代码：
递归法：

class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
        
        if(root == NULL) return 0;//空树
    
        if(root ->left == NULL && root ->right == NULL) return 0;//叶子节点

        int leftValue = sumOfLeftLeaves(root ->left);//传入左子树
        if(root ->left != NULL && root ->left->left == NULL && root ->left ->right == NULL)
        { // 左子树就是一个左叶子的情况
            leftValue = root ->left ->val;//
        }
        int rightValue = sumOfLeftLeaves(root ->right);

        //把左子树和右子树的左叶子结点的值相加，得到最终值
        int sum = leftValue + rightValue;
        return sum;
    }

};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

迭代法：

class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
        stack<TreeNode*> stackA;
        int result = 0;
        if(root == NULL) return 0;
        stackA.push(root);
        while(!stackA.empty())
        {
            
            TreeNode* Node = stackA.top();
            stackA.pop();
            if(Node ->left != NULL && Node ->left ->left == NULL && Node ->left ->right == NULL)
            {
                result += Node ->left ->val;
            }
            if(Node ->right != NULL) stackA.push(Node ->right);
            if(Node ->left != NULL) stackA.push(Node ->left);
        }
        return result;
    }

};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23