[Leetcode][JAVA] Sum Root to Leaf Numbers

Given a binary tree containing digits from0-9only, each root-to-leaf path could represent a number.An example is the root-to-leaf path1->2->3which represents the number123.Find the tota...

weixin_30318645

37人浏览 · 2014-10-27 06:52:00

weixin_30318645 · 2014-10-27 06:52:00 发布

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.

最开始把这题当回溯法题目做了，就是收集所有的路径和，然后加起来。后来发现其实如果到了叶子节点后把值传给上层就成了类似分治法的方法，代码也比较简洁：

 1     public int sumNumbers(TreeNode root) {
 2          return sumN(root,0);
 3     }
 4     public int sumN(TreeNode nd, int v)
 5     {
 6         if(nd==null)
 7             return 0;
 8         if(nd.left==null && nd.right==null)
 9             return v*10+nd.val;
10         return sumN(nd.left, v*10+nd.val)+sumN(nd.right, v*10+nd.val);
11     }

如果不上传值到上层，就用一个变量保存总和, 代码如下：

 1     public int sumNumbers(TreeNode root) {
 2          sumN(root,0);
 3          return sum;
 4     }
 5     int sum=0;
 6     public void sumN(TreeNode nd, int v)
 7     {
 8         if(nd==null)
 9             return;
10         if(nd.left==null && nd.right==null)
11             sum += v*10+nd.val;
12         sumN(nd.left, v*10+nd.val);
13         sumN(nd.right, v*10+nd.val);
14     }