首页 > 代码库 > Sum Root to Leaf Numbers
Sum Root to Leaf Numbers
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.
这道题，我是在先序遍历的基础上改的，添加了一个类似堆栈的list，如果是非叶子节点将其“入栈”，如果是叶子节点node“弹栈”直到node的父亲节点出现，扫描“栈底”到“栈顶”所有元素组成的数字，计算sum。直到前序遍历结束
1 import java.util.ArrayList; 2 import java.util.List; 3 4 5 6 7 class TreeNode { 8 int val; 9 TreeNode left;10 TreeNode right;11 TreeNode(int x) { val = x; }12 }13 14 public class Solution {15 16 List<TreeNode> list = new ArrayList<TreeNode>();17 18 int sum = 0;19 20 public int sumNumbers(TreeNode root) {21 if(null == root) //空树返回022 return 0;23 else if(null == root.left && null == root.right){//只有根节点返回根节点的值24 return root.val;25 }else{26 preOrder(root); //至少有一个子树27 // list.add(root); //根节点入栈28 }29 30 return sum;31 }32 33 /**34 * 前序遍历树35 * @param root36 */37 public void preOrder(TreeNode root){38 if(root == null)39 return;40 if(null == root.left && root.right == null){//叶子节点41 while(list.size() != 0 && root != list.get(list.size() - 1).left && root != list.get(list.size() - 1).right){42 list.remove(list.size() - 1);43 }44 int temp = 0;45 for(int i = 0; i < list.size(); i++){ //计算一个数46 temp = temp * 10 + list.get(i).val;47 }48 temp = temp * 10 + root.val; //叶子节点加上去49 //System.out.println("temp = " + temp);50 sum += temp; //计算和51 if(root == list.get(list.size() - 1).right){ //如果叶子节点是右子树，出栈52 list.remove(list.size() - 1);53 }54 }55 else{ //非叶子节点56 while(list.size() != 0 && root != list.get(list.size() - 1).left && root != list.get(list.size() - 1).right){57 list.remove(list.size() - 1);58 } //root应该与栈顶元素相同59 list.add(root);60 preOrder(root.left);61 preOrder(root.right);62 }63 }64 }
题目提示的是用DFS，一会儿百度一下~
看了一下discuss里面的，这个写的挺漂亮的
public class Solution { public int sumNumbers(TreeNode root) { return preOrder(root, 0); } public int preOrder(TreeNode root, int val){ if(root == null) return 0; val = val * 10 + root.val; if(null == root.left && null == root.right) return val; else return preOrder(root.left, val) + preOrder(root.right, val); }}
Sum Root to Leaf Numbers
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。