112、路径总和
给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
说明: 叶子节点是指没有子节点的节点。
示例:
给定如下二叉树，以及目标和 sum = 22，
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。
题解
由于叶子节点是指没有子节点的节点，所以递归有节的结束应该为：
if (root.left == null && root.right == null) {
return root.val == sum;
}
1、深度优先遍历，回溯，左右根遍历
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean hasPathSum(TreeNode root, int sum) {
if (root == null) {
return false;
}
if (root.left == null && root.right == null) {
return root.val == sum;
}
return hasPathSum(root.left,sum - root.val) || hasPathSum(root.right,sum - root.val);
}
}
113、路径总和 II
给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
说明: 叶子节点是指没有子节点的节点。
示例:
给定如下二叉树，以及目标和 sum = 22，
5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
返回:
[
[5,4,11,2],
[5,8,4,5]
]
通过次数51,438提交次数86,050
题解
由于叶子节点是指没有子节点的节点，所以递归有节的结束应该为：
if (root.left == null && root.right == null) {
return root.val == sum;
}
1、深度优先遍历，回溯，左右根遍历
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
// 不带回溯
class Solution {
List<List<Integer>> res = new ArrayList<List<Integer>>();
public List<List<Integer>> pathSum(TreeNode root, int sum) {
if (root == null) {
return res;
}
hasPathSumCore(root,sum,new ArrayList<>());
return res;
}
private void hasPathSumCore(TreeNode root, int sum,List<Integer> tmp) {
if (root == null) {
return;
}
if (root.left == null && root.right == null) {
if (root.val == sum) {
tmp.add(root.val);
res.add(new ArrayList<Integer>(tmp));
}
return;
}
tmp.add(root.val);
hasPathSumCore(root.left,sum - root.val,new ArrayList<Integer>(tmp));
hasPathSumCore(root.right,sum - root.val,new ArrayList<Integer>(tmp));
}
}
// 带回溯的
class Solution {
public List<List<Integer>> pathSum(TreeNode root, int sum) {
List<List<Integer>> result = new LinkedList<>();
List<Integer> curPath = new LinkedList<>();
recur(result, curPath, root, sum);
return result;
}
private void recur(List<List<Integer>> result, List<Integer> curPath, TreeNode curNode, int sum){
if(curNode == null){
return;
}
curPath.add(curNode.val);
if(curNode.val == sum && curNode.left == null && curNode.right == null){
result.add(new ArrayList<>(curPath));
}else{
recur(result, curPath, curNode.left, sum - curNode.val);
recur(result, curPath, curNode.right, sum - curNode.val);
}
curPath.remove(curPath.size() - 1);
}
}
// 作者：donoghl
// 链接：https://leetcode-cn.com/problems/path-sum-ii/solution/java-dfs-2-by-donoghl/
437、路径总和 III
给定一个二叉树，它的每个结点都存放着一个整数值。
找出路径和等于给定数值的路径总数。
路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
二叉树不超过1000个节点，且节点数值范围是 [-1000000,1000000] 的整数。
示例：
root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
10
/ \
5 -3
/ \ \
3 2 11
/ \ \
3 -2 1
返回 3。和等于 8 的路径有:
1. 5 -> 3
2. 5 -> 2 -> 1
3. -3 -> 11
题解
因为可以不用从根节点开始，所以递归里面包着递归去搜索。对于每个节点，都从头开始搜索。
1、双递归
- 递归，递归开始节点
- 子递归，搜索解
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int pathSum(TreeNode root,int sum) {
if (root == null) {
return 0;
}
int result = searchPath(root,sum);
int left = pathSum(root.left,sum);
int right = pathSum(root.right,sum);
return result + left + right;
}
private int searchPath(TreeNode null,int sum) {
if (root == null) {
return 0;
}
sum = sum - root.val;
int result = sum == 0 ? 1 : 0;
return result + searchPath(root.left,sum) + searchPath(root.right, sum);
}
}
// 作者：ming-zhi-shan-you--m9RfkvKDad
// 链接：https://leetcode-cn.com/problems/path-sum-iii/solution/437lu-jing-zong-he-iii-di-gui-fang-shi-by-ming-zhi/
2、前缀和 + 深度优先搜索
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int pathSum(TreeNode root, int sum) {
return helper(root, sum, new int[1000], 0);
}
private int helper(TreeNode root, int sum, int[] a, int depth) {
if (root == null) {
return 0;
}
int num = root.val == sum ? 1 : 0;
int tmp = root.val;
// 利用前缀和，计算是否存在解
for (int i = depth - 1; i >= 0; i--) {
tmp += a[i];
if (tmp == sum) {
num++;
}
}
a[depth] = root.val;
int left = helper(root.left, sum, a, depth + 1);
int right = helper(root.right, sum, a, depth + 1);
return num + left + right;
}
}
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com
