Lipsky

LeetCode 404. Sum of Left Leaves 左叶子结点值之和

字数统计: 289阅读时长: 1 min
2020/02/20 Share

404. 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.

Resolution#

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

}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
* Java
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/

class Solution {
public int sumOfLeftLeaves(TreeNode root) {
if(root == null){
return 0;
}
if(root.left != null && root.left.left == null && root.left.right == null){
return root.left.val + sumOfLeftLeaves(root.right);
}
return sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right);
}
}

Time Complexity: $O(n)$

Space Complexity: $O(h)$

note:recursion

The algrithm above is based on how to sum value of all nodes.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int sumOfTrees(TreeNode root){
if(root == null){
return 0;
}
/*
//get all value of leaves.
int sum = 0;
if(root.left == null && root.right == null){
sum = root.val;
}
*/
int sum = root.val;
int left = sumOfTrees(root.left);
int right = sumOfTrees(root.right);
return sum + left + right;

}
CATALOG
  1. 1. 404. Sum of Left Leaves 左叶子结点值之和#
  • Example:#
  • Resolution#