404.左叶子之和

力扣题目链接(opens new window)

计算给定二叉树的所有左叶子之和。

示例：

404.左叶子之和1

思路

首先要注意是判断左叶子，不是二叉树左侧节点，所以不要上来想着层序遍历。

因为题目中其实没有说清楚左叶子究竟是什么节点，那么我来给出左叶子的明确定义：如果左节点不为空，且左节点没有左右孩子，那么这个节点的左节点就是左叶子

大家思考一下如下图中二叉树，左叶子之和究竟是多少？

404.左叶子之和

其实是0，因为这棵树根本没有左叶子！

那么判断当前节点是不是左叶子是无法判断的，必须要通过节点的父节点来判断其左孩子是不是左叶子。

如果该节点的左节点不为空，该节点的左节点的左节点为空，该节点的左节点的右节点为空，则找到了一个左叶子，判断代码如下：

1
2
3
if (node->left != NULL && node->left->left == NULL && node->left->right == NULL) {
    左叶子节点处理逻辑
}

递归法

递归的遍历顺序为后序遍历（左右中），是因为要通过递归函数的返回值来累加求取左叶子数值之和。。

递归三部曲：

  1. 确定递归函数的参数和返回值

判断一个树的左叶子节点之和，那么一定要传入树的根节点，递归函数的返回值为数值之和，所以为int

使用题目中给出的函数就可以了。

  1. 确定终止条件

依然是

1
if (root == NULL) return 0;
  1. 确定单层递归的逻辑

当遇到左叶子节点的时候，记录数值，然后通过递归求取左子树左叶子之和，和 右子树左叶子之和，相加便是整个树的左叶子之和。

代码如下：

1
2
3
4
5
6
7
8
9
int leftValue = sumOfLeftLeaves(root->left);    // 左
int rightValue = sumOfLeftLeaves(root->right);  // 右
                                                // 中
int midValue = 0;
if (root->left && !root->left->left && !root->left->right) {
    midValue = root->left->val;
}
int sum = midValue + leftValue + rightValue;
return sum;

整体递归代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
        if (root == NULL) return 0;

        int leftValue = sumOfLeftLeaves(root->left);    // 左
        int rightValue = sumOfLeftLeaves(root->right);  // 右
                                                        // 中
        int midValue = 0;
        if (root->left && !root->left->left && !root->left->right) { // 中
            midValue = root->left->val;
        }
        int sum = midValue + leftValue + rightValue;
        return sum;
    }
};

以上代码精简之后如下：

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
        if (root == NULL) return 0;
        int midValue = 0;
        if (root->left != NULL && root->left->left == NULL && root->left->right == NULL) {
            midValue = root->left->val;
        }
        return midValue + sumOfLeftLeaves(root->left) + sumOfLeftLeaves(root->right);
    }
};

Java代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
	public int sumOfLeftLeaves(TreeNode root) {
        if(root == null) return 0;
        int left = sumOfLeftLeaves(root.left);
        int right = sumOfLeftLeaves(root.right);
        int value = 0;
        if(root.left != null && root.left.left == null && root.left.right == null) {
            value = root.left.val;
        }
        return left + right + value;
    }
}

迭代法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
	public int sumOfLeftLeaves(TreeNode root) {
		if(root == null) return 0;
        int res = 0;
		Deque<TreeNode> que = new LinkedList<>();
		que.offer(root);
		while(!que.isEmpty()) {
			TreeNode node = que.poll();
			if(node.left != null && node.left.left == null && node.left.right == null) res += node.left.val;
            if(node.left != null) que.offer(node.left);
            if(node.right != null) que.offer(node.right);
		}
        return res;
        
	}
}