LeetCode – Sum Root to Leaf Numbers (Java)
Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number. Find the total sum of all root-to-leaf numbers.
For example,
The root-to-leaf path 1->3 represents the number 13.
Return the sum = 12 + 13 = 25.
The idea is to do a preorder traversal of the tree. In the preorder traversal, keep track of the value calculated till the current node, let this value be val. For every node, we update the val as val*10 plus node’s data.
http://www.cnblogs.com/springfor/p/3884038.html
1 int sumhelper(TreeNode root, int levelBase) {
2 if(root == null)
3 return 0;
4
5 if(root.left == null && root.right == null) {
6 return levelBase + root.val;
7 }
8
9 int nextLevelBase = (levelBase + root.val)*10 ;
10 int leftSubTreeSum = sumhelper(root.left, nextLevelBase);
11 int rightSubTreeSum = sumhelper(root.right, nextLevelBase);
12
13 return leftSubTreeSum + rightSubTreeSum;
14 }
15
16 public int sumNumbers(TreeNode root) {
17 return sumhelper(root,0);
18 }
http://www.programcreek.com/2014/05/leetcode-sum-root-to-leaf-numbers-java/
X. BFS
https://leetcode.com/discuss/1711/can-you-improve-this-algorithm
https://leetcode.com/discuss/26723/simple-no-recursive-using-queue-java
I used 2 queues to do a breadth first traversal. both time and space complexity is O(N):
public int sumNumbers(TreeNode root) { int total = 0; LinkedList<TreeNode> q = new LinkedList<TreeNode>(); LinkedList<Integer> sumq = new LinkedList<Integer>(); if(root !=null){ q.addLast(root); sumq.addLast(root.val); } while(!q.isEmpty()){ TreeNode current = q.removeFirst(); int partialSum = sumq.removeFirst(); if(current.left == null && current.right==null){ total+=partialSum; }else{ if(current.right !=null){ q.addLast(current.right); sumq.addLast(partialSum*10+current.right.val); } if(current.left !=null){ q.addLast(current.left); sumq.addLast(partialSum*10+current.left.val); } } } return total; }
X. https://leetcode.com/discuss/29260/non-recursive-preorder-traverse-java-solution
public int sumNumbers(TreeNode root) { if(root==null){ return 0; } int sum = 0; TreeNode curr; Stack<TreeNode> ws = new Stack<TreeNode>(); ws.push(root); while(!ws.empty()){ curr = ws.pop(); if(curr.right!=null){ curr.right.val = curr.val*10+curr.right.val; ws.push(curr.right); } if(curr.left!=null){ curr.left.val = curr.val*10+curr.left.val; ws.push(curr.left); } if(curr.left==null && curr.right==null){ // leaf node sum+=curr.val; } } return sum; }
http://www.geeksforgeeks.org/sum-numbers-formed-root-leaf-paths/
http://bangbingsyb.blogspot.com/2014/11/leetcode-sum-root-to-leaf-numbers.html
Java: use array, so we can update the parameter.
Or we can use class instance variable.
Or pass and return- check previous code.
==> talk or think about different approaches
public int sumNumbers(TreeNode root) {
if (root==null){
return 0;
}
int[] sum={0};
int current=0;
getSum(root,current, sum);
return sum[0];
}
public void getSum(TreeNode root, int current, int[] sum){
if (root==null){
return;
}
current=current*10+root.val;
if (root.left==null && root.right==null){
sum[0]=sum[0]+current;
return;
}
getSum(root.left, current, sum);
getSum(root.right, current, sum);
}
Read full article from LeetCode – Sum Root to Leaf Numbers (Java)
Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number. Find the total sum of all root-to-leaf numbers.
For example,
The root-to-leaf path 1->2 represents the number 12.1 / \ 2 3
The root-to-leaf path 1->3 represents the number 13.
Return the sum = 12 + 13 = 25.
The idea is to do a preorder traversal of the tree. In the preorder traversal, keep track of the value calculated till the current node, let this value be val. For every node, we update the val as val*10 plus node’s data.
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 sum = dfs(node.left, num, sum) + dfs(node.right, num, sum); return sum; } |
1 int sumhelper(TreeNode root, int levelBase) {
2 if(root == null)
3 return 0;
4
5 if(root.left == null && root.right == null) {
6 return levelBase + root.val;
7 }
8
9 int nextLevelBase = (levelBase + root.val)*10 ;
10 int leftSubTreeSum = sumhelper(root.left, nextLevelBase);
11 int rightSubTreeSum = sumhelper(root.right, nextLevelBase);
12
13 return leftSubTreeSum + rightSubTreeSum;
14 }
15
16 public int sumNumbers(TreeNode root) {
17 return sumhelper(root,0);
18 }
http://www.programcreek.com/2014/05/leetcode-sum-root-to-leaf-numbers-java/
public int sumNumbers(TreeNode root) { int result = 0; if(root==null) return result; ArrayList<ArrayList<TreeNode>> all = new ArrayList<ArrayList<TreeNode>>(); ArrayList<TreeNode> l = new ArrayList<TreeNode>(); l.add(root); dfs(root, l, all); for(ArrayList<TreeNode> a: all){ StringBuilder sb = new StringBuilder(); for(TreeNode n: a){ sb.append(String.valueOf(n.val)); } int currValue = Integer.valueOf(sb.toString()); result = result + currValue; } return result; } public void dfs(TreeNode n, ArrayList<TreeNode> l, ArrayList<ArrayList<TreeNode>> all){ if(n.left==null && n.right==null){ ArrayList<TreeNode> t = new ArrayList<TreeNode>(); t.addAll(l); all.add(t); } if(n.left!=null){ l.add(n.left); dfs(n.left, l, all); l.remove(l.size()-1); } if(n.right!=null){ l.add(n.right); dfs(n.right, l, all); l.remove(l.size()-1); } } |
X. BFS
https://leetcode.com/discuss/1711/can-you-improve-this-algorithm
https://leetcode.com/discuss/26723/simple-no-recursive-using-queue-java
I used 2 queues to do a breadth first traversal. both time and space complexity is O(N):
public int sumNumbers(TreeNode root) { int total = 0; LinkedList<TreeNode> q = new LinkedList<TreeNode>(); LinkedList<Integer> sumq = new LinkedList<Integer>(); if(root !=null){ q.addLast(root); sumq.addLast(root.val); } while(!q.isEmpty()){ TreeNode current = q.removeFirst(); int partialSum = sumq.removeFirst(); if(current.left == null && current.right==null){ total+=partialSum; }else{ if(current.right !=null){ q.addLast(current.right); sumq.addLast(partialSum*10+current.right.val); } if(current.left !=null){ q.addLast(current.left); sumq.addLast(partialSum*10+current.left.val); } } } return total; }
X. https://leetcode.com/discuss/29260/non-recursive-preorder-traverse-java-solution
public int sumNumbers(TreeNode root) { if(root==null){ return 0; } int sum = 0; TreeNode curr; Stack<TreeNode> ws = new Stack<TreeNode>(); ws.push(root); while(!ws.empty()){ curr = ws.pop(); if(curr.right!=null){ curr.right.val = curr.val*10+curr.right.val; ws.push(curr.right); } if(curr.left!=null){ curr.left.val = curr.val*10+curr.left.val; ws.push(curr.left); } if(curr.left==null && curr.right==null){ // leaf node sum+=curr.val; } } return sum; }
http://www.geeksforgeeks.org/sum-numbers-formed-root-leaf-paths/
// Returns sum of all root to leaf paths. The first parameter is root// of current subtree, the second parameter is value of the number formed// by nodes from root to this nodeint treePathsSumUtil(struct node *root, int val){ // Base case if (root == NULL) return 0; // Update val val = (val*10 + root->data); // if current node is leaf, return the current value of val if (root->left==NULL && root->right==NULL) return val; // recur sum of values for left and right subtree return treePathsSumUtil(root->left, val) + treePathsSumUtil(root->right, val);}// A wrapper function over treePathsSumUtil()int treePathsSum(struct node *root){ // Pass the initial value as 0 as there is nothing above root return treePathsSumUtil(root, 0);}
当root->leaf path很长时，path num将会很大，sum的时候很容易出现溢出。
需要和面试官讨论是否要特殊处理这样的情况。另外当root为NULL时需要返回0.
Use bigInteger.
Cdoing is about what may go wrong - here the number may
Cdoing is about what may go wrong - here the number may
Root to leaf path sum equal to a given number
int sumNumbers(TreeNode *root) { int sum = 0; sumRootToLeafNum(root, 0, sum); return sum; } void sumRootToLeafNum(TreeNode *root, int curNum, int &sum) { if(!root) return; curNum = curNum*10 + root->val; if(!root->left && !root->right) sum += curNum; if(root->left) sumRootToLeafNum(root->left, curNum, sum); if(root->right) sumRootToLeafNum(root->right, curNum, sum); }http://rleetcode.blogspot.com/2014/03/sum-root-to-leaf-numbersjava-and-python.html
Java: use array, so we can update the parameter.
Or we can use class instance variable.
Or pass and return- check previous code.
==> talk or think about different approaches
public int sumNumbers(TreeNode root) {
if (root==null){
return 0;
}
int[] sum={0};
int current=0;
getSum(root,current, sum);
return sum[0];
}
public void getSum(TreeNode root, int current, int[] sum){
if (root==null){
return;
}
current=current*10+root.val;
if (root.left==null && root.right==null){
sum[0]=sum[0]+current;
return;
}
getSum(root.left, current, sum);
getSum(root.right, current, sum);
}
Read full article from LeetCode – Sum Root to Leaf Numbers (Java)
