LeetCode 112&113&437 Path Sum I&II&III
原创LeetCode 112&113&437 Path Sum I&II&III
原创
112.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.
Note: A leaf is a node with no children.
Example:
Given the below binary tree and sum = 22,
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.
题目大意：判断是否存在一条从根节点到叶子的路径，使得和等于sum;
解法：
public boolean hasPathSum(TreeNode root, int sum) {
if (root == null) return false;
if(root.left == null && root.right == null){
if (root.val == sum) return true;
else return false;
}else {
return hasPathSum(root.left,sum-root.val)|| hasPathSum(root.right,sum-root.val);
}
}113.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.
Note: A leaf is a node with no children.
Example:
Given the below binary tree and sum = 22,
5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1Return:
[
[5,4,11,2],
[5,8,4,5]
]题目大意：将所有满足和为sum的路径罗列出来。
解法：
public List<List<Integer>> pathSum(TreeNode root, int sum) {
List<List<Integer>> res = new LinkedList<>();
List<Integer> res_temp = new LinkedList<>();
pathSum_recursion(res_temp,root,sum,res);
return res;
}
public void pathSum_recursion(List<Integer> res_temp,TreeNode root, int sum,List<List<Integer>> res){
if (root == null) return;
res_temp.add(root.val);
if (root.right==null &&root.left==null&&root.val == sum) { //如果是叶子节点
res.add(new LinkedList<>(res_temp));
}
//不是叶子节点
pathSum_recursion(res_temp,root.left, sum-root.val,res);
pathSum_recursion(res_temp,root.right, sum-root.val,res);
res_temp.remove(res_temp.size()-1);
}437.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题目大意:问有多路径满足和为sum，注意这里的路径不一定要从root节点到叶子节点。
解法：
public int pathSum(TreeNode root, int sum) {
if (root == null) return 0;
return findPath(root,sum) + pathSum(root.left,sum)+pathSum(root.right,sum);
}
public int findPath(TreeNode node ,int sum){
if (node ==null) return 0;
int res = 0;
if (node.val == sum) {
res += 1;
}
return res+ findPath(node.left,sum - node.val)+findPath(node.right,sum - node.val);
}
扩展：
打印二叉树的所有路径
解法：
public List<List<Integer>> binaryTreePaths(TreeNode root) {
List<List<Integer>> res = new LinkedList<>();
List<Integer> resTemp = new ArrayList<>();
binaryTreePathHelper(root,resTemp,res);
return res;
}
public void binaryTreePathHelper(TreeNode root,List<Integer> resTemp , List<List<Integer>> res){
if (root == null) return;
resTemp.add(root.val);
if (root.left == null && root.right== null){
res.add(new LinkedList<>(resTemp));
}
binaryTreePathHelper(root.left,resTemp,res);
binaryTreePathHelper(root.right,resTemp,res);
resTemp.remove(resTemp.size()-1);
}这个与《113.Path Sum II》类似，首先将节点添加进来，再判断是否满足条件，然后递归左右子树，最后一定要删除掉最后一个元素。对应程序中的：
resTemp.remove(resTemp.size()-1);其实这个也就是一个回溯的过程，为了让回溯的过程更加清楚，设置了一个测试用例：
5
/ \
3 6
/ \ \
2 4 7
/
1每一次执行 resTemp.remove(resTemp.size()-1);所删除的节点分别是：
1
2
4
3
7
6
5实际上也就是后序删除所有的节点。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
腾讯云开发者
