LeetCode404. Sum of Left Leaves（二叉树 / 搜索）

LeetCode404. Sum of Left Leaves（二叉树 / 搜索）

• Easy
• Accepted：117,885
• Submissions：241,857

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.

链接

https://leetcode.com/problems/sum-of-left-leaves

题意

给定一棵二叉树，求所有的左叶子结点的值之和。

题解

因为题目要求的是左叶子的结点，所以我们应该在左叶子结点的上一层就做相应的处理。即对于当前结点如果其左儿子已经是叶子结点，那么就可以返回左儿子的值了，但是注意不要忘了该结点的右子树。如果左儿子不是叶子结点那么就接着往下递归。

每个结点访问一次，平均时间复杂度依然是$O(n)$。

代码

• Runtime: 8 ms, faster than 100.00% of C++ online submissions for Sum of Left Leaves.
• Memory Usage: 14.1 MB, less than 43.28% of C++ online submissions for Sum of Left Leaves.

class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
        if (root == NULL)
            return 0;
        TreeNode* rootLeft = root->left;
        if (rootLeft != NULL && rootLeft->left == NULL && rootLeft->right == NULL)
            return rootLeft->val + sumOfLeftLeaves(root->right);
        int leftSum = sumOfLeftLeaves(root->left);
        int rightSum = sumOfLeftLeaves(root->right);
        return leftSum + rightSum;
    }
};

当然还可以有更简单的写法，根本不需要rootLeft、leftSum和rightSum等变量。

The end.
2019年3月15日 星期五