echo

任生命穿梭 时间的角落

0%

左叶子之和

Posted on In Valine:

404. 左叶子之和

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

示例：

1
2
3
4
5
6
7
    3
   / \
  9  20
    /  \
   15   7

在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24

我们可以很快写出所有叶子之和的递归代码：

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {

    public int sumOfLeftLeaves(TreeNode root) {
        if(root == null){
            return 0;
        }
        if(root.left == null && root.right == null){
			return root.val;
        }
        return sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right);
    }
}

一个叶子是否为左叶子只有它的父节点知道，我们使用 father 来维护父节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    //父结点指针
    TreeNode father = null;

    public int sumOfLeftLeaves(TreeNode root) {
        if(root == null){
            return 0;
        }
        if(root.left == null && root.right == null){
            //判断当前叶子是否为左叶子
            if(father != null && father.left == root){
                return root.val;
            }else{
                return 0;
            }
        }
        //更新父节点
        father = root;
        return sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right);
    }
}