LeetCode404-Sum of Left Leaves

题目

Find the sum of all left leaves in a given binary tree.

Example:

    3
   / \
  9  20
    /  \
   15   7

There are two left leaves in the binary tree, with values 9 and 15 respectively. Return 24.

分析

本题目要求二叉树中所有左叶子节点的数值和,显然这符合递归定义。如果要求一棵以root为根的树的和sum,那么只要求到了左子树的sum_l以及右子树的sum_r,即能得到sum = sum_l + sum_r。而问题关键不在这,而是如何寻找递归的出口并返回值。可以发现:

  • 如果root为空,返回0是很自然的
  • 如果某root的root.left和root.right均为空,说明它是叶子节点
  • 如果满足上面第二个条件,且这个root正是它父节点的左子,说明它是左叶子节点,返回节点的val值

代码

public class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        
        //判断root是否为空
        if (root == null)
            return 0;
        
        int leftSum = 0;
        int rightSum = 0;
        
        //考察root的左子树是否为叶节点
        TreeNode leftRoot = root.left;
        TreeNode rightRoot = root.right;
        if (leftRoot != null && leftRoot.left == null && leftRoot.right == null) //是否为叶节点
            leftSum = leftRoot.val; //叶节点,返回左子树和
        else
            leftSum = sumOfLeftLeaves(leftRoot); //递归计算左子树和
             
        rightSum = sumOfLeftLeaves(rightRoot); //递归计算右子树和
        
        return  leftSum + rightSum;
    }
}

Leave a Comment.