129. Sum Root to Leaf Numbers

  • 35.5%

https://leetcode.com/problems/sum-root-to-leaf-numbers/?tab=Description

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path 1->2->3 which represents the number 123.

Find the total sum of all root-to-leaf numbers.

1
2
3
4
5
6
7
8
9
For example,

1
/ \
2 3
The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.

Return the sum = 12 + 13 = 25.

方法一:

56ms, 46.63%, July 15th, 2016

https://discuss.leetcode.com/topic/12048/5-ms-c-code-using-dfs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
* 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 sumNumbers(TreeNode* root) {
if(!root) return 0;
sum = 0;
DFS(root, 0);
return sum;
}

void DFS(TreeNode *&node, int currentSum){
currentSum = currentSum * 10 + node->val;
if(!node->left && !node->right)
sum += currentSum;
if(node->left)
DFS(node->left, currentSum);
if(node->right)
DFS(node->right, currentSum);
}

private:
int sum;
};

我的代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
* 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 sumNumbers(TreeNode* root) {
int res = 0, cur = 0;
helper(root, res, cur);
return res;
}

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

方法二:

https://discuss.leetcode.com/topic/3025/one-of-the-easier-solution-using-preorder-traversal-recursion

One of the easier solution using preorder traversal (recursion)

The idea is to do a preorder traversal of the tree. In the preorder traversal, keep track of the value calculated till the current node, let this value be val. For every node, we update the val as val10 plus node’s data.*

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
int sumNumbers(TreeNode *root) {
return sumNumberUtil(root,0);

}
// preorder
int sumNumberUtil(struct TreeNode* node, int val)
{
if(node==NULL)
return 0;

val= val*10+node->val;
if(node->left==NULL && node->right==NULL)
{
return val;
}

return sumNumberUtil(node->left,val)+sumNumberUtil(node->right, val);
}
};

python


76ms, 10.56%, July 15th, 2016

https://discuss.leetcode.com/topic/21363/python-solutions-dfs-stack-bfs-queue-dfs-recursively

Python solutions (dfs+stack, bfs+queue, dfs recursively).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# dfs + stack
def sumNumbers1(self, root):
if not root:
return 0
stack, res = [(root, root.val)], 0
while stack:
node, value = stack.pop()
if node:
if not node.left and not node.right:
res += value
if node.right:
stack.append((node.right, value*10+node.right.val))
if node.left:
stack.append((node.left, value*10+node.left.val))
return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# bfs + queue
def sumNumbers2(self, root):
if not root:
return 0
queue, res = collections.deque([(root, root.val)]), 0
while queue:
node, value = queue.popleft()
if node:
if not node.left and not node.right:
res += value
if node.left:
queue.append((node.left, value*10+node.left.val))
if node.right:
queue.append((node.right, value*10+node.right.val))
return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# recursively 
def sumNumbers(self, root):
self.res = 0
self.dfs(root, 0)
return self.res

def dfs(self, root, value):
if root:
#if not root.left and not root.right:
# self.res += value*10 + root.val
self.dfs(root.left, value*10+root.val)
#if not root.left and not root.right:
# self.res += value*10 + root.val
self.dfs(root.right, value*10+root.val)
if not root.left and not root.right:
self.res += value*10 + root.val

java


solution 1:

1ms, 28.00%, July 15th, 2016

https://discuss.leetcode.com/topic/6731/short-java-solution-recursion

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
* 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 sumNumbers(TreeNode root) {
return sum(root, 0);
}

public int sum(TreeNode n, int s){
if(n==null) return 0;
if(n.right == null && n.left == null) return s*10 + n.val;
return sum(n.left, s*10+n.val) + sum(n.right, s*10 + n.val);
}
}

solution 2:

1ms, 28.00%, July 15th, 2016

https://discuss.leetcode.com/topic/644/can-you-improve-this-algorithm

Can you improve this algorithm?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
* 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 sumNumbers(TreeNode root) {
if (root == null)
return 0;
return sumR(root, 0);
}
public int sumR(TreeNode root, int x) {
if (root.right == null && root.left == null)
return 10 * x + root.val;
int val = 0;
if (root.left != null)
val += sumR(root.left, 10 * x + root.val);
if (root.right != null)
val += sumR(root.right, 10 * x + root.val);
return val;
}
}

谢谢你,可爱的朋友。