MENU

LeetCode404. Sum of Left Leaves(二叉树 / 搜索)

2019 年 03 月 15 日 • 阅读: 815 • LeetCode阅读设置

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日 星期五
最后编辑于: 2019 年 03 月 23 日