easy medium
https://leetcode.com/problems/path-sum/
https://leetcode.com/problems/path-sum-ii/
相关题 Path III,区别在于path可以树中任意路径上的节点,所以2次dfs,多的一次用来计算树中非root的pathSum http://rainykat.blogspot.com/2017/01/leetcode-437-path-sum-iii-2dfs.html
113.
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] ]
112只要返回有无路径,return true or false
public class Solution { public boolean hasPathSum(TreeNode root, int sum) { if(root == null)return false; if(root.left == null && root.right == null && sum - root.val == 0) return true; return hasPathSum(root.left, sum - root.val)||hasPathSum(root.right, sum - root.val); } }
113需要存下path, back track path
public class Solution { public List<List<Integer>> pathSum(TreeNode root, int sum) { List<List<Integer>> res = new ArrayList<List<Integer>>(); if(root == null)return res; helper(root, res, new ArrayList<Integer>(), sum); return res; } public void helper(TreeNode root, List<List<Integer>> res, List<Integer> path, int sum){ if(root == null)return; path.add(root.val); if(root.left == null && root.right == null && sum - root.val == 0) res.add(new ArrayList<>(path)); helper(root.left, res, path, sum - root.val); helper(root.right, res, path, sum - root.val); path.remove(path.size()-1); } }
No comments:
Post a Comment