Question

Formatted question description: https://leetcode.ca/all/129.html

129	Sum Root 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.

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.

@tag-tree

Algorithm

Use DFS recursion to solve this problem because it is not simply adding the numbers of each node, but every time a new child node is encountered, the number of the parent node must be multiplied by 10 times and then added to next recursion.

If traversing to the leaf node, return the current accumulation result sum. If not, call the recursive function on its left and right child nodes respectively, and add the two results to return.

Code

Java

public class Sum_Root_to_Leaf_Numbers {

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

	public class Solution_even_better {

	    int sum = 0;
	    public int sumNumbers(TreeNode root) {
	        // directly pass prev*10+val
	        if (root == null) {
	            return 0;
            }

	        find(root, 0);

	        return sum;
	    }

	    public void find(TreeNode root, int prev) {
	        if (root.left == null && root.right == null) {
                sum += prev * 10 + root.val;
            }

	        if (root.left != null) {
	            find(root.left, prev * 10 + root.val);
            }
	        if (root.right != null) {
	            find(root.right, prev * 10 + root.val);
            }
	    }
	}


	public class Solution_optimized {

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

	        return dfs(root, 0, 0);
	    }

	    public int dfs(TreeNode node, int num, int sum){
	        if(node == null) {
	            return sum;
	        }

	        num = num * 10 + node.val;

	        // leaf
	        if(node.left == null && node.right == null) {
	            sum += num;
	            return sum;
	        }

	        // left subtree + right subtree
	        // @note: here is the great part, sum is never being updated until reaching a leaf node
	        //          so, it can pass corner cases like [1,0], where one side of real-root is null but sum for this side is 0
	        int newSum = dfs(node.left, num, sum) + dfs(node.right, num, sum);
	        return newSum;
	    }

	}


	public class Solution {
	    int sum = 0;

	    public int sumNumbers(TreeNode root) {

	        if (root == null) {
	            return sum;
	        }

	        // @note: key is to root-to-leaft, so at least depth=2
	        // so I just arbitrarily check root node
	        if (root.left == null && root.right == null) {
	            return root.val;
	        }

	        if (root.left != null) {
	            traverse(root.left, root.val);

	        }
	        if (root.right != null) {
	            traverse(root.right, root.val);
	        }

	        return sum;
	    }

	    private void traverse(TreeNode root, int currentSum) {
	        if (root.left == null && root.right == null) {
	            sum += currentSum * 10 + root.val;
	        }

	        if (root.left != null) {
	            traverse(root.left, currentSum * 10 + root.val);

	        }
	        if (root.right != null) {
	            traverse(root.right, currentSum * 10 + root.val);
	        }
	    }
	}


}

// OJ: https://leetcode.com/problems/sum-root-to-leaf-numbers/
// Time: O(N)
// Space: O(H)
class Solution {
    int ans = 0;
    void dfs(TreeNode *root, int sum) {
        if (!root) return;
        sum = sum * 10 + root->val;
        if (!root->left && !root->right) ans += sum;
        dfs(root->left, sum);
        dfs(root->right, sum);
    }
public:
    int sumNumbers(TreeNode* root) {
        dfs(root, 0);
        return ans;
    }
};

# 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.sum = 0

    def dfs(root, pathsum):
      if root:
        pathsum += root.val
        left = dfs(root.left, pathsum * 10)
        right = dfs(root.right, pathsum * 10)
        if not left and not right:
          self.sum += pathsum
        return True

    dfs(root, 0)
    return self.sum

129 - Sum Root to Leaf Numbers

Question

Algorithm

Code

All Problems

All Solutions