Leetcode 112/113/437. Path Sum
参考：剑指offer 26：二叉树中和为某一值的路径
112：
Given a binary tree and a sum, determineif the tree has a root-to-leaf path such that adding up all the values alongthe 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 aroot-to-leaf path 5->4->11->2 which sumis 22.
这道题是为了判断二叉树中有没有从顶到叶子节点的一个路径，使得路径上的值的和为目标值。
分析：很简单，不需要记录路径，直接使用递归
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public boolean hasPathSum(TreeNode root, int sum){ if(root==null){ return false; } if(root.right==null&&root.left==null){ return (sum==root.val); } boolean b1=(root.left!=null)?(hasPathSum(root.left,sum-root.val)):false; boolean b2=(root.right!=null)?(hasPathSum(root.right,sum-root.val)):false; return b1||b2; } }113：
Given a binary tree and a sum, find allroot-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]
]
这个题比上个题稍微难了一些，需要给出路径了。
分析：我们可以使用一个栈来暂存路径。同样使用递归（前序遍历）来遍历二叉树。当用前序遍历的方式访问到某一节点时，我们把该节点添加到路径上。如果该节点为叶子节点并且路径中的值的和正好等于目标值，则当前路径符合要求，存到我们的res中。 如果当前节点不是叶子节点，则访问其子节点。子节点访问结束后，需要在暂存栈弹出当前节点。
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public List<List<Integer>> pathSum(TreeNode root, int sum) { ArrayList<List<Integer>> res=new ArrayList<List<Integer>>(); Stack<Integer> cache=new Stack<Integer>(); if(root==null){ return res; } respathSum(root,sum,cache,res); return res; } public void respathSum(TreeNode root,int sum,Stack<Integer> cache,ArrayList<List<Integer>> res){ cache.push(root.val); if(root.left==null&&root.right==null&&root.val==sum){ Stack <Integer> s=new Stack<Integer>(); s.addAll(cache); res.add(s); } if(root.left!=null){ respathSum(root.left,sum-root.val,cache,res); } if(root.right!=null){ respathSum(root.right,sum-root.val,cache,res); } cache.pop(); } }
437
You are given a binary tree in which each node contains an integervalue.
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 therange -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这个题又比上个题要难一点，路径可能不从根节点开始，也可能不在叶子节点结束。但是不需要所有路径，只需要给出可能的路径值就行了。这里同样使用递归（前序遍历），同样需要注意在处理完左右子节点之后，需要一个回到父节点状态的操作。
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public int pathSum(TreeNode root, int sum) { if(root==null){ return 0; } ArrayList <Integer> a=new ArrayList<Integer>(); Para p=new Para(); p.cache=0; p.a=a; p.sum=sum; respathSum(root,p); return p.cache; } public void respathSum(TreeNode root,Para p){ for(int i=0;i<(p.a).size();i++){ (p.a).set(i,(p.a).get(i)+root.val); } (p.a).add(root.val); for(int i:(p.a)){ if(i==p.sum){ p.cache++; } } if(root.left!=null){ respathSum(root.left,p); } if(root.right!=null){ respathSum(root.right,p); } for(int i=0;i<(p.a).size();i++){ (p.a).set(i,(p.a).get(i)-root.val); } (p.a).remove((p.a).size()-1); } } class Para{ ArrayList<Integer> a; int cache; int sum; }
