Thursday, January 15, 2015

Sum Root to Leaf Numbers (LeetCode Tree)

Question: 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.

Idea: Depth-first search. Use a class member variable to record the result. Calculate the partial results along the search. Once a leaf is visited, update the total result.

Time: O(n) Space: O(lgn)

Code: 
 public class Solution {  
   int result;  
   public int sumNumbers(TreeNode root) {  
     result=0;  
     int lastSum=0;  
     dfs(lastSum,root);  
     return result;  
   }  
   public void dfs(int lastSum,TreeNode cur)  
   {  
     if(cur==null)  
       return;  
     if(cur.left==null&&cur.right==null)  
     {  
       result+=lastSum*10+cur.val;  
       return;  
     }  
     dfs(lastSum*10+cur.val,cur.left);  
     dfs(lastSum*10+cur.val,cur.right);  
   }  
 }  

No comments:

Post a Comment