摘要:解题思路本题要求所有从根结点到叶子节点的路径和,我们用递归实现。结束条件当遇到叶子节点时,直接结束,返回计算好的如果遇到空节点,则返回数值。
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.
解题思路
本题要求所有从根结点到叶子节点的路径和,我们用递归实现。
结束条件:当遇到叶子节点时,直接结束,返回计算好的sum;如果遇到空节点,则返回数值0。
2.代码
public class Solution { public int sumNumbers(TreeNode root) { return sum(root,0); } private int sum(TreeNode root, int cur){ if(root==null) return 0; cur=10*cur+root.val; if(root.left==null&&root.right==null) return cur; else return sum(root.left,cur)+sum(root.right,cur); } }
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/69812.html
摘要:解题思路利用递归,对于每个根节点,只要左子树和右子树中有一个满足,就返回每次访问一个节点,就将该节点的作为新的进行下一层的判断。代码解题思路本题的不同点是可以不从开始,不到结束。代码当前节点开始当前节点左节点开始当前节点右节点开始 Path SumGiven a binary tree and a sum, determine if the tree has a root-to-lea...
Problem 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 tota...
摘要:递归法复杂度时间空间递归栈空间思路简单的二叉树遍历,遍历时将自身的数值加入子节点。一旦遍历到叶子节点便将该叶子结点的值加入结果中。 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...
摘要:解题思路用递归实现很简单,对于每个根节点,最大深度就等于左子树的最大深度和右子树的最大深度的较大值。解题思路本题的注意点在于如果某个根节点有一边的子树为空,那么它的深度就等于另一边不为空的子树的深度,其他的逻辑与上一题相同。 Maximum Depth of Binary TreeGiven a binary tree, find its maximum depth. The maxi...
摘要:但是本题的难点在于,使用递归实现,但是前面的第四种情况不能作为递归函数的返回值,所以我们需要定义两个值,代表单边路径的最大值,用于递归用于和回路的较大值。 Binary Tree Maximum Path SumGiven a binary tree, find the maximum path sum. For this problem, a path is defined as a...
阅读 928·2021-11-23 09:51
阅读 993·2021-11-18 10:02
阅读 1908·2021-09-10 11:27
阅读 3138·2021-09-10 10:51
阅读 778·2019-08-29 15:13
阅读 2064·2019-08-29 11:32
阅读 2501·2019-08-29 11:25
阅读 3044·2019-08-26 11:46