(第31天)【leetcode题解】404、左叶子之和

404、左叶子之和

题目描述

给定二叉树的根节点 root ，返回所有左叶子之和。

思路

1. 题目分析：

• 判断左叶子节点：A节点的左孩子不为空，且左孩子的左右孩子都为空，那么这个左孩子节点就是左叶子节点。

2.递归法：

• 递归函数的功能：返回以root为根节点的树的左叶子节点值之和。
• 参数和返回值：root表示(树或子树)根节点、返回int左叶子节点之和
• 终止条件：如果root为空，则以其为根节点的树的左叶子节点一定为空，返回0。
• 递归逻辑：后序遍历。因为要通过函数返回值来累加左叶子节点值。

3.迭代法：

• 在遍历过程中识别左叶子节点，并把左叶子节点的值累加。
• 任意一种遍历方式都可。

代码

递归法：

class Solution {
public:
    //返回以root为根节点的树的左叶子节点值之和
    int sumOfLeftLeaves(TreeNode* root) {
        if (root == nullptr) return 0;//root为空，则该树的叶子节点也为空


        int leftValue = sumOfLeftLeaves(root->left); // 左子树所有左叶子节点值之和
        if (root->left != nullptr && root->left->left == nullptr && root->left->right == nullptr) {
            //判断root->left是否是左叶子
            leftValue = root->left->val;//得到左叶子的值
        }
        int rightValue = sumOfLeftLeaves(root->right); //右子树的所有左叶子节点值之和

        int sum = leftValue + rightValue; // 得到以当前root节点为根节点的树的左叶子节点值之和
        return sum;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

迭代法：

class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
        stack<TreeNode*> st;
        if (root != nullptr) st.push(root);
        int result = 0;
        while (!st.empty()) {
            TreeNode* node = st.top(); 
            st.pop();
            if (node->left != NULL && node->left->left == NULL && node->left->right == NULL) {
                result += node->left->val;  
            }
            if (node->right) st.push(node->right);
            if (node->left) st.push(node->left);
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18