Given a binary tree, each node contains a number from 10 to 9, and each path from root to leaf represents a number. For example, the root to leaf path 1->2->3 represents the number 123. Computes the sum of all numbers generated from the root to the leaf node.

Note: Leaf nodes are nodes that have no child nodes.

Example 1:

Input:1.2.3]
    1
   / \
  2   3Output:25Path from root to leaf node1->2On behalf of the digital12.Path from root to leaf node1->3On behalf of the digital13.So the sum of the numbers is equal to12 + 13 = 25.
Copy the code

Example 2:

Input:4.9.0.5.1]
    4
   / \
  9   0
 / \
5   1Output:1026Path from root to leaf node4->9->5On behalf of the digital495.Path from root to leaf node4->9->1On behalf of the digital491.Path from root to leaf node4->0On behalf of the digital40.So the sum of the numbers is equal to495 + 491 + 40 = 1026.
Copy the code

The title requires the sum of the numbers represented by the paths from each root node to leaf node. Therefore, we need to traverse all possible paths from the root node depth, record the val of the nodes on the path, and finally count the sum of the numbers represented by each path. Simple thought, direct code:

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

class Solution:
    def sumNumbers(self, root: TreeNode) - >int:
        if not root: return 0
        
        r = []

        def track(root, path) :
            if not root: return 
			
            if not root.left and not root.right:  The leaf node has been reached
                path.append(str(root.val))   # complete one path
                for i in range(len(path)):   # remove possible '0'
                    ifpath[i] ! ='0':  
                        r.append(eval(' '.join(path[i:])))  # Use eval() to get a string value of type int and save it to r
                        break
                path.pop()   # the pop-up
                return

            path.append(str(root.val))  # to make choices
            track(root.left, path)    Walk through the left subtree
            track(root.right, path)   Walk through the right subtree
            path.pop()   # undo select

        track(root, [])

        return sum(r)    # sum
Copy the code

Or accumulate the val value of the node directly in path and save it at last, as shown below:

class Solution:
    def sumNumbers(self, root: TreeNode) - >int:
        if not root: return 0
        
        r = []
        def track(root, path) :
            if not root: return 
            if not root.left and not root.right:
                path = path * 10 + root.val
                r.append(path)
                path = (path - root.val) / 10
                return

            path = path * 10 + root.val
            track(root.left, path)
            track(root.right, path)
            path = (path - root.val) / 10

        track(root, 0)

        return sum(r)
Copy the code

The corresponding Java solution code is as follows:

class Solution {
    public int number = 0;
    public int sumNumbers(TreeNode root) {
        if(root == null) {return 0;
        }

        track(root, number);
        return number;
    }

    public void track(TreeNode root, int n){
        if(root == null) {return;
        }

        if(root.left == null && root.right == null){
            n = n * 10 + root.val;
            number += n;
            n = (n - root.val) / 10;
            return;
        }
        
        n = n * 10 + root.val;
        track(root.left, n);
        track(root.right, n);
        n = (n - root.val) / 10; }}Copy the code