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.

Note: A leaf is a node with no children.

Example:

Input: [1,2,3]

    1

   / \

  2   3

Output: 25

Explanation:

The root-to-leaf path 1->2 represents the number 12.

The root-to-leaf path 1->3 represents the number 13.

Therefore, sum = 12 + 13 = 25.

Example 2:

Input: [4,9,0,5,1]

    4

   / \

  9   0

 / \

5   1

Output: 1026

Explanation:

The root-to-leaf path 4->9->5 represents the number 495.

The root-to-leaf path 4->9->1 represents the number 491.

The root-to-leaf path 4->0 represents the number 40.

Therefore, sum = 495 + 491 + 40 = 1026.

给一个只含有数字0-9的二叉树，每一个从根节点到叶节点的路径代表一个数字，求所有这些数字的和。

解法1：递归，累加所有路径上节点的值，每多一层之前的值要扩大十倍。

解法2: 迭代，while循环，用stack或queue来存下一层的节点和之前的和。TLE

Java:

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);

}

Python:

# Time:  O(n)

# Space: O(h), h is height of binary tree

class TreeNode(object):

    def __init__(self, x):

        self.val = x

        self.left = None

        self.right = None

class Solution(object):

    # @param root, a tree node

    # @return an integer

    def sumNumbers(self, root):

        return self.sumNumbersRecu(root, 0)

    def sumNumbersRecu(self, root, num):

        if root is None:

            return 0

        if root.left is None and root.right is None:

            return num * 10 + root.val

        return self.sumNumbersRecu(root.left, num * 10 + root.val) + self.sumNumbersRecu(root.right, num * 10 + root.val)

Python: bfs + 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

Python: 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

Python: Recursive

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

C++:

/**

 * Definition for binary tree

 * struct TreeNode {

 *     int val;

 *     TreeNode *left;

 *     TreeNode *right;

 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}

 * };

 */

class Solution {

public:

    int sumNumbers(TreeNode *root) {

        return sumNumbersDFS(root, 0);

    }

    int sumNumbersDFS(TreeNode *root, int sum) {

        if (!root) return 0;

        sum = sum * 10 + root->val;

        if (!root->left && !root->right) return sum;

        return sumNumbersDFS(root->left, sum) + sumNumbersDFS(root->right, sum);

    }

};