Tuesday, December 16, 2014

Sum Root to Leaf Numbers

A typical tree traversal problem. The number formed by the path = root.val (1) * 100 + root.left.val * 10  + leaf.val. Thus when traverse down the tree, just add current subtree's root value to the 10 times of the previous sum, for each subtree, and we are done!


public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
  }
 
public class SumofTree {
    public int sumNumbers(TreeNode root) {
        return getSum(root, 0);
        
    }
    private int getSum(TreeNode root, int prev_sum)
    {
        if (root == null)
            return 0;
        int sum = prev_sum * 10 + root.val;
        if (root.left == null && root.right == null)
            return sum;
        
        return getSum(root.left, sum) + getSum(root.right, sum);
    }
}

No comments:

Post a Comment