摘要:解题思路利用递归,对于每个根节点,只要左子树和右子树中有一个满足,就返回每次访问一个节点,就将该节点的作为新的进行下一层的判断。代码解题思路本题的不同点是可以不从开始,不到结束。代码当前节点开始当前节点左节点开始当前节点右节点开始
Path Sum
Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.
For example:
Given the below binary tree and sum = 22,
5 / 4 8 / / 11 13 4 / 7 2 1
return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.
1.解题思路
利用递归,对于每个根节点,只要左子树和右子树中有一个满足,就返回true;
每次访问一个节点,就将sum-该节点的val,作为新的Sum进行下一层的判断。
直到叶子节点,且sum与节点val相等,则表示存在这样的path,返回true.
2.代码
public class Solution { public boolean hasPathSum(TreeNode root, int sum) { if(root==null)return false; if(root.val==sum&&root.left==null&&root.right==null) return true; return hasPathSum(root.left,sum-root.val)||hasPathSum(root.right,sum-root.val); } }
Path Sum II
Given a binary tree and a sum, find all root-to-leaf paths where each path"s sum equals the given sum.
For example:
Given the below binary tree and sum = 22,
5 / 4 8 / / 11 13 4 / / 7 2 5 1
return
[
[5,4,11,2],
[5,8,4,5]
]
1.解题思路
本题是上一题的扩展,需要列出所有满足条件的path.我们只要在递归函数里添加List
2.代码
public class Solution { List> res=new ArrayList
>(); public List
> pathSum(TreeNode root, int sum) { if(root==null) return res; helper(root,sum,new ArrayList
()); return res; } private void helper(TreeNode root, int sum,List pre){ if(root==null) return; List cur=new ArrayList (pre); cur.add(root.val); if(root.left==null&&root.right==null&&sum==root.val){ res.add(cur); return; } helper(root.left,sum-root.val,cur); helper(root.right,sum-root.val,cur); } }
Path Sum III
You are given a binary tree in which each node contains an integer value.
Find the number of paths that sum to a given value.
The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).
The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.
Example:
root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8 10 / 5 -3 / 3 2 11 / 3 -2 1 Return 3. The paths that sum to 8 are: 1. 5 -> 3 2. 5 -> 2 -> 1 3. -3 -> 11
1.解题思路
本题的不同点是path可以不从root开始,不到leaf结束。但由于可以存在负数节点,所以没法通过比较大小来缩进节点,所以我们就只能考虑从每一个节点开始的情况。
2.代码
public class Solution { public int pathSum(TreeNode root, int sum) { if(root==null) return 0; //helper(root,sum) 当前节点开始 //pathSum(root.left,sum) 当前节点左节点开始 //pathSum(root.right,sum) 当前节点右节点开始 return helper(root,sum)+pathSum(root.left,sum)+pathSum(root.right,sum); } private int helper(TreeNode root,int sum){ if(root==null) return 0; int count=0; if(root.val==sum) count++; return count+helper(root.left,sum-root.val)+helper(root.right,sum-root.val); } }
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/69805.html
摘要: 112. Path Sum Problem Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum. Note: A leaf is a node...
摘要:只要我们能够有一个以某一中间路径和为的哈希表,就可以随时判断某一节点能否和之前路径相加成为目标值。 最新更新请见:https://yanjia.me/zh/2019/01/... Path Sum I Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that addin...
摘要:在线网站地址我的微信公众号完整题目列表从年月日起,每天更新一题,顺序从易到难,目前已更新个题。这是项目地址欢迎一起交流学习。 这篇文章记录我练习的 LeetCode 题目,语言 JavaScript。 在线网站:https://cattle.w3fun.com GitHub 地址:https://github.com/swpuLeo/ca...我的微信公众号: showImg(htt...
摘要:此时,若也正好减小为,说明当前集合是正解,加入数组。两个无法得到正解的情况是在为,而不为时,当然已经无法得到正解,。在不为而却已经小于等于的情况下,此时仍要加入其它数以令为,而要加入的数都是到的正整数,所以已无法满足令为的条件,。 Combination Sum I & II: link Combination Sum III Problem Find all possible com...
摘要:解题思路本题要求所有从根结点到叶子节点的路径和,我们用递归实现。结束条件当遇到叶子节点时,直接结束,返回计算好的如果遇到空节点,则返回数值。 Sum Root to Leaf NumbersGiven a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a numbe...
阅读 3653·2021-09-07 10:19
阅读 3596·2021-09-03 10:42
阅读 3555·2021-09-03 10:28
阅读 2516·2019-08-29 14:11
阅读 766·2019-08-29 13:54
阅读 1547·2019-08-29 12:14
阅读 377·2019-08-26 12:12
阅读 3578·2019-08-26 10:45