资讯专栏INFORMATION COLUMN

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

立即前往
首页/文章专栏/[LeetCode] Path Sum (I & II & III)

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

张金宝 / 1822人阅读

摘要：

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 with no children.

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.

Solution Recursive 
</>复制代码 
  1. class Solution {
  2.     public boolean hasPathSum(TreeNode root, int sum) {
  3.         if (root == null) return false;
  4.         //has to be a root-to-leaf path
  5.         if (root.val == sum && root.left == null && root.right == null) return true;
  6.         return hasPathSum(root.left, sum-root.val) || hasPathSum(root.right, sum-root.val);
  7.     }
  8. }
Update 2018-11 Solution Iterative 
</>复制代码 
  1. class Solution {
  2.     public boolean hasPathSum(TreeNode root, int sum) {
  3.         if (root == null) return false;
  4.         Deque nodestack = new ArrayDeque<>();
  5.         Deque sumstack = new ArrayDeque<>();
  6.         nodestack.push(root);
  7.         sumstack.push(sum);
  8.         while (!nodestack.isEmpty()) {
  9.             TreeNode curNode = nodestack.pop();
  10.             int curSum = sumstack.pop();
  11.             if (curNode.left == null && curNode.right == null && curNode.val == curSum) return true;
  12.             if (curNode.right != null) {
  13.                 nodestack.push(curNode.right);
  14.                 sumstack.push(curSum-curNode.val);
  15.             }
  16.             if (curNode.left != null) {
  17.                 nodestack.push(curNode.left);
  18.                 sumstack.push(curSum-curNode.val);
  19.             }
  20.         }
  21.         return false;
  22.     }
  23. }
Path Sum II Problem

Given a binary tree and a sum, find all root-to-leaf paths where each path"s sum equals the given sum.

Note: A leaf is a node with no children.

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:

</>复制代码 
  1. [
  2.    [5,4,11,2],
  3.    [5,8,4,5]
  4. ]
Solution 
</>复制代码 
  2. class Solution {
  3.     public List> pathSum(TreeNode root, int sum) {
  4.         List> res = new ArrayList<>();
  5.         if (root == null) return res;
  6.         dfs(root, sum, new ArrayList(), res);
  7.         return res;
  8.     }
  9.     private void dfs(TreeNode root, int sum, List temp, List> res) {
  10.         if (sum == root.val && root.left == null && root.right == null) {
  11.             temp.add(root.val);
  12.             List save = new ArrayList<>(temp); //important
  13.             res.add(save);
  14.             temp.remove(temp.size()-1);
  15.         } else {
  16.             temp.add(root.val);
  17.             if (root.left != null) dfs(root.left, sum-root.val, temp, res);
  18.             if (root.right != null) dfs(root.right, sum-root.val, temp, res);
  19.             temp.remove(temp.size()-1);
  20.         }
  21.         
  22.     }
  23. }
Path Sum III Problem

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

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

Return 3. The paths that sum to 8 are:

5 -> 3

5 -> 2 -> 1

-3 -> 11

Solution 
</>复制代码 
  1. class Solution {
  2.     public int pathSum(TreeNode root, int sum) {
  3.         if (root == null) return 0;
  4.         return helper(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
  5.     }
  6.     private int helper(TreeNode root, int sum) {        
  7.         int count = 0;
  8.         if (sum == root.val) count++;
  9.         if (root.left != null) count += helper(root.left, sum-root.val);
  10.         if (root.right != null) count += helper(root.right, sum-root.val);
  11.         return count;
  12.     }
  13. }
GPU云服务器 云服务器 i+1&lti java if&lt&gt js iframe&ampamp asp &amp&amp逻辑

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

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

相关文章

  • [Leetcode] Path Sum I &amp; II &amp; 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

  • [LintCode/LeetCode] Combination Sum I &amp; II

    摘要：和唯一的不同是组合中不能存在重复的元素，因此，在递归时将初始位即可。 Combination Sum I Problem Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T...

    ThreeWords 评论0 收藏0

  • [Leetcode-Tree] Path Sum I II III

    摘要：解题思路利用递归，对于每个根节点，只要左子树和右子树中有一个满足，就返回每次访问一个节点，就将该节点的作为新的进行下一层的判断。代码解题思路本题的不同点是可以不从开始，不到结束。代码当前节点开始当前节点左节点开始当前节点右节点开始 Path SumGiven a binary tree and a sum, determine if the tree has a root-to-lea...

    notebin 评论0 收藏0

  • [LeetCode] 4Sum &amp; 4Sum II

    摘要：和方法一样，多一个数，故多一层循环。完全一致，不再赘述， 4Sum Problem Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which ...

    sydMobile 评论0 收藏0

  • H-Index &amp; II

    H-Index 题目链接：https://leetcode.com/problems... sort： public class Solution { public int hIndex(int[] citations) { if(citations == null || citations.length == 0) return 0; // sort ...

    mochixuan 评论0 收藏0

发表评论

登陆后可评论

0条评论

张金宝

男|高级讲师
我要私信

TA的文章

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