题目描述

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.

解法一

思路

既然是二叉树的遍历问题，那想必是递归了。再看需要返回sum，对于递归来说就是先收集递归的结果，再加上自己的结果后返回，那就是后序遍历了，模板就是：

def sumOfLeftLeaves(root):
    ...
    sum = self.sumOfLeftLeaves(root.left) + self.sumOfLeftLeaves(root.right)
    # TODO
    return sum

题目要求的是处理左叶子结点，那么首先要解决的就是在递归中如何判断当前结点是否是左叶子结点了。很可惜的是，对于结点本身，虽然可以很容易判断其是否为叶子结点，但不能判断其是否为左结点。这里有个解决办法就是，既然遍历会遍历到每个结点，那不妨对每个结点检查其左子节点是不是叶子结点就好了，即：

if root.left and root.left.left is None and root.left.right is None:
    # TODO

这题的解法就出来啦。

Python

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None


class Solution(object):
    def sumOfLeftLeaves(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if root is None:
            return 0
        sum = self.sumOfLeftLeaves(root.left) + self.sumOfLeftLeaves(root.right)
        if root.left and root.left.left is None and root.left.right is None:
            sum += root.left.val
        return sum

Java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int sum = sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right);
        if (root.left != null && root.left.left == null && root.left.right == null) {
            sum += root.left.val;
        }
        return sum;
    }
}

C++

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int sumOfLeftLeaves(TreeNode *root) {
        if (root == nullptr) {
            return 0;
        }
        int sum = sumOfLeftLeaves(root->left) + sumOfLeftLeaves(root->right);
        if (root->left && root->left->left == nullptr && root->left->right == nullptr) {
            sum += root->left->val;
        }
        return sum;
    }
};