首页 > 代码库 > 【leetcode刷题笔记】Sum Root to Leaf Numbers
【leetcode刷题笔记】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
.
题解:
一开始的想法是计算每个节点到叶节点可以得到的整数的列表,然后返回给该节点的父节点,然后通过这个列表计算父节点到叶节点可以生成的整数,但是这种方法有个问题就是在计算父节点*10^x+子节点到页节点生成的整数的时候不能确定x的值,因为不知道父节点到叶节点的距离。所以这种方法不可行。
后来想了下,有个更简单的方法:将最终生成的整数存放在叶节点而不是根节点。每次递归的时候,在当前节点计算一个sum,表示从根节点到当前节点生成的整数,然后把这个sum传递给当前节点的孩子,在孩子上递归的计算从根节点到孩子节点生成的整数.....
举个例子,如下图所示的一棵树:
最后将各个节点上的sum相加(123+125+146)就得到了最终的答案。
代码如下:
1 /** 2 * Definition for binary tree 3 * public class TreeNode { 4 * int val; 5 * TreeNode left; 6 * TreeNode right; 7 * TreeNode(int x) { val = x; } 8 * } 9 */10 public class Solution {11 private int totalSum = 0;12 private void rootList(TreeNode root,int sum){13 if(root == null)14 return;15 sum = sum*10+root.val;16 17 if(root.left == null && root.right == null)18 {19 totalSum += sum;20 return;21 }22 23 rootList(root.left, sum);24 rootList(root.right, sum);25 26 }27 public int sumNumbers(TreeNode root) {28 rootList(root, 0);29 return totalSum;30 }31 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。