题目:计算给定二叉树的所有左叶子之和。
3
/ \
9 20
/ \
15 7
在这个二叉树中,有两个左叶子,分别是 9 和 15,所以返回 24
二叉树遍历一般用递归来解决,主要是找到递归结束的点,
本次左叶子之和=右子树的左叶子之和+左子树的左叶子之和。
左叶子
- 叶子:没有左边节点,没有右边节点,并且当前节点是小根的左节点
递归的终止条件:
当前结点为空,返回0(空结点当然值为0)
当前结点是个子叶结点且是个左子叶root.left == null && root.right == null && isLeftLeave,返回其本身的值参与相加。
参考:https://leetcode-cn.com/problems/sum-of-left-leaves/solution/404java-di-gui-die-dai-by-ustcyyw/需要增加一个判断,判断当前是不是左节点,因为有可能,右边节点,的左右子树都是空,它其实是右节点的计算结果
public int sumOfLeftLeaves(TreeNode root) {
return sumOfLeftLeavesHelper(root,false);
}
public int sumOfLeftLeavesHelper(TreeNode root,Boolean flag){
if(null==root){
return 0;
}
if(root.left==null && root.right==null && flag){
return root.val;
}
return sumOfLeftLeavesHelper(root.left,true)+sumOfLeftLeavesHelper(root.right,false);
}