资讯专栏INFORMATION COLUMN

上云采购季！| 2核2G4M爆款云服务器低至59元/年，更有多台、长期优惠，快来选购！

立即前往
首页/文章专栏/[Leetcode-Tree] Path Sum I II III

[Leetcode-Tree] Path Sum I II III

notebin / 1194人阅读

摘要：解题思路利用递归，对于每个根节点，只要左子树和右子树中有一个满足，就返回每次访问一个节点，就将该节点的作为新的进行下一层的判断。代码解题思路本题的不同点是可以不从开始，不到结束。代码当前节点开始当前节点左节点开始当前节点右节点开始

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,

</>复制代码 
  1.       5
  2.      / 
  3.     4   8
  4.    /   / 
  5.   11  13  4
  6.  /        
  7. 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.代码

</>复制代码 
  1. public class Solution {
  2.     public boolean hasPathSum(TreeNode root, int sum) {
  3.         if(root==null)return false;
  4.         if(root.val==sum&&root.left==null&&root.right==null) return true;
  5.         return hasPathSum(root.left,sum-root.val)||hasPathSum(root.right,sum-root.val);
  6.         
  7.     }
  8.    
  9. }

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,

</>复制代码 
  1.           5
  2.          / 
  3.         4   8
  4.        /   / 
  5.       11  13  4
  6.      /      / 
  7.     7    2  5   1

return
[
[5,4,11,2],
[5,8,4,5]
]

1.解题思路

本题是上一题的扩展，需要列出所有满足条件的path.我们只要在递归函数里添加List pre参数来存储已经生成的节点序列即可。

2.代码

</>复制代码 
  1. public class Solution {
  2.     List> res=new ArrayList>();
  3.     public List> pathSum(TreeNode root, int sum) {
  4.         if(root==null) return res;
  5.         helper(root,sum,new ArrayList());
  6.         return res;
  7.     }
  8.     private void helper(TreeNode root, int sum,List pre){
  9.         if(root==null) return;
  10.         List cur=new ArrayList(pre);
  11.         cur.add(root.val);
  12.         if(root.left==null&&root.right==null&&sum==root.val){
  13.             res.add(cur);
  14.             return;
  15.         }
  16.        
  17.         helper(root.left,sum-root.val,cur);
  18.         helper(root.right,sum-root.val,cur);
  19.     }
  20. }

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:

</>复制代码 
  1. root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
  2.       10
  3.      /  
  4.     5   -3
  5.    /     
  6.   3   2   11
  7.  /    
  8. 3  -2   1
  9. Return 3. The paths that sum to 8 are:
  10. 1.  5 -> 3
  11. 2.  5 -> 2 -> 1
  12. 3. -3 -> 11

1.解题思路

本题的不同点是path可以不从root开始，不到leaf结束。但由于可以存在负数节点，所以没法通过比较大小来缩进节点，所以我们就只能考虑从每一个节点开始的情况。

2.代码

</>复制代码 
  1. public class Solution {
  2.     public int pathSum(TreeNode root, int sum) {
  3.         if(root==null) return 0;
  4.         //helper(root,sum) 当前节点开始
  5.         //pathSum(root.left,sum) 当前节点左节点开始
  6.         //pathSum(root.right,sum) 当前节点右节点开始
  7.         return helper(root,sum)+pathSum(root.left,sum)+pathSum(root.right,sum);
  8.        
  9.     }
  10.     private int helper(TreeNode root,int sum){
  11.        if(root==null) return 0;
  12.        int count=0;
  13.        if(root.val==sum) count++;
  14.        return count+helper(root.left,sum-root.val)+helper(root.right,sum-root.val);
  15.     }
  16. }
GPU云服务器 云服务器 III II ii6 ii7

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/69805.html

相关文章

  • [LeetCode] Path Sum (I & II & III)

    摘要： 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...

    张金宝 评论0 收藏0

  • [Leetcode] Path Sum I & II & III 路径和1,2,3

    摘要：只要我们能够有一个以某一中间路径和为的哈希表，就可以随时判断某一节点能否和之前路径相加成为目标值。 最新更新请见：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...

    caiyongji 评论0 收藏0

  • 前端 | 每天一个 LeetCode

    摘要：在线网站地址我的微信公众号完整题目列表从年月日起，每天更新一题，顺序从易到难，目前已更新个题。这是项目地址欢迎一起交流学习。 这篇文章记录我练习的 LeetCode 题目，语言 JavaScript。 在线网站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公众号： showImg(htt...

    张汉庆 评论0 收藏0

  • [LeetCode] Combination Sum III | Combination Sum I

    摘要：此时，若也正好减小为，说明当前集合是正解，加入数组。两个无法得到正解的情况是在为，而不为时，当然已经无法得到正解，。在不为而却已经小于等于的情况下，此时仍要加入其它数以令为，而要加入的数都是到的正整数，所以已无法满足令为的条件，。 Combination Sum I & II: link Combination Sum III Problem Find all possible com...

    leiyi 评论0 收藏0

  • [Leetcode-Tree] Sum Root to Leaf Numbers

    摘要：解题思路本题要求所有从根结点到叶子节点的路径和，我们用递归实现。结束条件当遇到叶子节点时，直接结束，返回计算好的如果遇到空节点，则返回数值。 Sum Root to Leaf NumbersGiven a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a numbe...

    BigNerdCoding 评论0 收藏0

发表评论

登陆后可评论

0条评论

notebin

男|高级讲师
我要私信

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<