卖萌的弱渣

I am stupid, I am hungry.

Sum Roof to Leaf Numbers

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.

Example

1
2
3

    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.

Solution

  • Recursive
  • Java
(Sum-Root-to-Leaf-Numbers.java) download
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);
}
}
  • Tranverse the tree and record the value for each path
(Sum-Root-to-Leaf-Numbers.py) download
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
32
33
34

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def sumNumbers(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if not root:
            return 0
        val = []
        self.findVal(val,root,0)
        ret = 0
        for i in val:
            ret += i
        return ret

    def findVal(self,val,root,tmp):
        if root == None:
            return

        tmp = tmp*10 + root.val
        if root.left == None and root.right == None:
            val.append(tmp)
            return

        self.findVal(val,root.left,tmp)
        self.findVal(val,root.right,tmp)
        return