404. Sum of Left Leaves

  • 46.4%

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

1
2
3
4
5
6
7
8
9
10
Example:

3
/ \
9 20
/ \
15 7

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

方法一:

我的代码实现

深度优先遍历,类似于先序遍历,等价于先序遍历加一个判断。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
int sumOfLeftLeaves(TreeNode* root) {
int res = 0;
helper(root, res);
return res;
}

void helper(TreeNode* root, int& res){
if(!root) return;
if(root->left!=NULL && root->left->left==NULL && root->left->right==NULL)
res += root->left->val;
helper(root->left, res);
helper(root->right, res);
}
};

方法二:

3-line c++ solution

递归,调用本身

1
2
3
4
5
6
7
8
class Solution {
public:
int sumOfLeftLeaves(TreeNode* root) {
if (!root) return 0;
if (root->left && !root->left->left && !root->left->right) return root->left->val + sumOfLeftLeaves(root->right);
return sumOfLeftLeaves(root->left) + sumOfLeftLeaves(root->right);
}
};

我的代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
* 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) return 0;
if(root->left && !root->left->left && !root->left->right)
return root->left->val + sumOfLeftLeaves(root->right);
return sumOfLeftLeaves(root->left) + sumOfLeftLeaves(root->right);
}
};

方法三:

3 line recursive c++ solution, no need to explain

1
2
3
4
5
int sumOfLeftLeaves(TreeNode* root, bool isleft = false) {
if (!root) return 0;
if (!root->left && !root->right) return isleft ? root->val : 0;
return sumOfLeftLeaves(root->left, true) + sumOfLeftLeaves(root->right, false);
}

https://discuss.leetcode.com/topic/60467/3-line-c-solution

3-line c++ solution

1
2
3
4
5
6
7
8
class Solution {
public:
int sumOfLeftLeaves(TreeNode* root) {
if (!root) return 0;
if (root->left && !root->left->left && !root->left->right) return root->left->val + sumOfLeftLeaves(root->right);
return sumOfLeftLeaves(root->left) + sumOfLeftLeaves(root->right);
}
};

https://discuss.leetcode.com/topic/60409/3-line-recursive-c-solution-no-need-to-explain

3 line recursive c++ solution, no need to explain

1
2
3
4
5
int sumOfLeftLeaves(TreeNode* root, bool isleft = false) {
if (!root) return 0;
if (!root->left && !root->right) return isleft ? root->val : 0;
return sumOfLeftLeaves(root->left, true) + sumOfLeftLeaves(root->right, false);
}

https://discuss.leetcode.com/topic/60395/4-lines-python-recursive-ac-solution

4 Lines Python Recursive AC Solution

base case => node is none

recursive case => Left child is / isn’t Leave

1
2
3
4
5
6
class Solution(object):
def sumOfLeftLeaves(self, root):
if not root: return 0
if root.left and not root.left.left and not root.left.right:
return root.left.val + self.sumOfLeftLeaves(root.right)
return self.sumOfLeftLeaves(root.left) + self.sumOfLeftLeaves(root.right) # isn't leave

EDIT:

Could be 3 Lines, but L2 would be too long.

谢谢你,可爱的朋友。