Alibi

My Life is Getting Better

Leetcode[129] Sum Root to Leaf Numbers

09 Nov 2015

###Task1 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.

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.

###Python ####O(n) space

# 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
        """
        ret = []
        self.findAll(root, ret, 0)
        return sum(ret)
    def findAll(self, root, ret, cur):
        if not root:
            return
        cur = cur * 10 + root.val
        if not root.left and not root.right:
            ret.append(cur)
            return
        self.findAll(root.left, ret, cur)
        self.findAll(root.right, ret, cur)

####O(1)space

# 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
        """
        self.ret = 0
        self.findAll(root, self.ret, 0)
        return self.ret
    def findAll(self, root, ret, cur):
        if not root:
            return
        cur = cur * 10 + root.val
        if not root.left and not root.right:
            self.ret += cur
            return
        self.findAll(root.left, self.ret, cur)
        self.findAll(root.right, self.ret, cur)

###Java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {

	public void sumHelper(TreeNode root, ArrayList<Integer> list, int crt) {
		int rootVal = root.val;
		crt = crt * 10 + rootVal;
		if (root.left == null && root.right == null) {
			list.add(crt);
			return;
		}
		if (root.left != null) {
			sumHelper(root.left, list, crt);
		}
		if (root.right != null) {
			sumHelper(root.right, list, crt);
		}
		
		return;
	}

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

        ArrayList<Integer> list = new ArrayList<Integer>();
        sumHelper(root, list, 0);

        int res = 0;
        for (int i: list) {
        	res += i;
        }

        return res;
    }
}

###Points

Related Posts