首页 > 代码库 > [Leetcode][JAVA] Sum Root to Leaf Numbers
[Leetcode][JAVA] 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.
最开始把这题当回溯法题目做了，就是收集所有的路径和，然后加起来。后来发现其实如果到了叶子节点后把值传给上层就成了类似分治法的方法，代码也比较简洁：
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 }
另外，使用栈进行DFS可以非递归地实现，代码比较复杂没有实现。。
[Leetcode][JAVA] Sum Root to Leaf Numbers
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。