路径总和
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。
叶子节点 是指没有子节点的节点。
递归
public boolean hasPathSum(TreeNode root, int targetSum) {
if (root == null) {
return false;
}
if (root.left == null && root.right == null) {
return targetSum == root.val;
}
return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val);
}
没有写成以下是因为，二叉树为空需要返回false
public boolean hasPathSum(TreeNode root, int targetSum) {
if (root == null) {
return targetSum == 0;
}
return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val);
}
迭代
public boolean hasPathSum(TreeNode root, int targetSum) {
if (root == null) {
return false;
}
Queue<TreeNode> queue = new LinkedList<>();
Queue<Integer> sumQueue = new LinkedList<>();
queue.add(root);
sumQueue.add(root.val);
while (!queue.isEmpty()) {
root = queue.poll();
int sum = sumQueue.poll();
if (root.left == null && root.right == null) {
if (sum == targetSum) {
return true;
}
} else {
if (root.left != null) {
queue.add(root.left);
sumQueue.add(sum + root.left.val);
}
if (root.right != null) {
queue.add(root.right);
sumQueue.add(sum + root.right.val);
}
}
}
return false;
}
路径总和 II
给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
叶子节点 是指没有子节点的节点。
示例:
给定如下二叉树，以及目标和
sum = 22，5 / \ 4 8 / / \ 11 13 4 / \ / \ 7 2 5 1返回:
[
[5,4,11,2],
[5,8,4,5]
]
递归
public List<List<Integer>> pathSum(TreeNode root, int sum) {
List<List<Integer>> ans = new ArrayList<>();
Stack<Integer> stack = new Stack<>();
trace(root, sum, 0, ans, stack);
return ans;
}
public void trace(TreeNode root, int sum, int partSum, List<List<Integer>> lists, Stack<Integer> stack) {
if (root == null) {
return;
}
partSum += root.val;
stack.push(root.val);
if (root.left == null && root.right == null) {
if (partSum == sum) {
lists.add(new ArrayList<>(stack));
}
}
trace(root.left, sum, partSum, lists, stack);
trace(root.right, sum, partSum, lists, stack);
partSum -= root.val;
stack.pop();
}
迭代
public List<List<Integer>> pathSum(TreeNode root, int target) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) {
return res;
}
Queue<TreeNode> queue = new LinkedList<>();
Queue<List<Integer>> pathQueue = new LinkedList<>();
queue.add(root);
pathQueue.add(new ArrayList<>(Arrays.asList(root.val, root.val)));
while (!queue.isEmpty()) {
root = queue.poll();
List<Integer> pathList = pathQueue.poll();
if (root.left == null && root.right == null) {
if (pathList.get(0) == target) {
pathList.remove(0);
res.add(pathList);
}
} else {
if (root.left != null) {
queue.add(root.left);
List<Integer> newPaths = new ArrayList<>(pathList);
newPaths.set(0, pathList.get(0) + root.left.val);
newPaths.add(root.left.val);
pathQueue.add(newPaths);
}
if (root.right != null) {
queue.add(root.right);
List<Integer> newPaths = new ArrayList<>(pathList);
newPaths.set(0, pathList.get(0) + root.right.val);
newPaths.add(root.right.val);
pathQueue.add(newPaths);
}
}
}
return res;
}
路径总和 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
方法一：两个DFS
先序遍历每一个结点，以每一个结点作为根寻找满足和的路径
private int count;
public int pathSum(TreeNode root, int sum) {
preOrder(root, sum);
return count;
}
public void preOrder(TreeNode root, int sum) {
if (root == null) {
return;
}
trace(root, sum, 0);
preOrder(root.left, sum);
preOrder(root.right, sum);
}
private void trace(TreeNode root, int sum, int partSum) {
if (root == null) {
return;
}
partSum += root.val;
if (partSum == sum) {
count++;
}
trace(root.left, sum, partSum);
trace(root.right, sum, partSum);
}
方法二：前缀和
如果前缀总和currSum，在节点A和节点B处相差target，则位于节点A和节点B之间的元素之和是target
private Map<Integer, Integer> map = new HashMap<>();//key:前缀和 value：次数
public int pathSum(TreeNode root, int sum) {
map.put(0, 1);
return trace(root, sum, 0);
}
private int trace(TreeNode root, int sum, int partSum) {
if (root == null) {
return 0;
}
partSum += root.val;
int ans = 0;
ans += map.getOrDefault(partSum - sum, 0);
map.put(partSum, map.getOrDefault(partSum, 0) + 1);
ans += trace(root.left, sum, partSum);
ans += trace(root.right, sum, partSum);
//回到本层，恢复状态，不再是前缀了
map.put(partSum, map.get(partSum) - 1);
return ans;
}
二叉树中的最大路径和
给定一个非空二叉树，返回其最大路径和。
本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。
示例 1:
输入: [1,2,3]
1
/ \
2 3
输出: 6
示例 2:
输入: [-10,9,20,null,null,15,7]
-10
/ \
9 20
/ \
15 7
输出: 42
每走到一个结点，有三个选择：
- 不走了
- 向左走
- 向右走
private int max = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
if (root == null) {
return 0;
}
dfs(root);
return max;
}
public int dfs (TreeNode root) {
if (root == null) {
return 0;
}
int left = Math.max(0, dfs(root.left));//为负数就不向下走了
int right = Math.max(0, dfs(root.right));
max = Math.max(max, left + right + root.val);
return root.val + Math.max(left, right);//以root为根直路的长度
}
二叉树的所有路径
给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。
叶子节点 是指没有子节点的节点。
示例 1：
输入：root = [1,2,3,null,5]
输出：["1->2->5","1->3"]
递归
private List<String> res = new ArrayList<>();
public List<String> binaryTreePaths(TreeNode root) {
dfs(root, new Stack<>());
return res;
}
private void dfs(TreeNode root, Stack<Integer> stack) {
if (root == null) {
return;
}
stack.add(root.val);
if (root.left == null && root.right == null) {
StringBuilder sb = new StringBuilder();
for (int v : stack) {
sb.append(v).append("->");
}
sb.delete(sb.length() - 2, sb.length());
res.add(sb.toString());
}
dfs(root.left, stack);
dfs(root.right, stack);
stack.pop();
}
迭代
public List<String> binaryTreePaths(TreeNode root) {
List<String> res = new ArrayList<>();
if (root == null) {
return res;
}
Queue<TreeNode> queue = new LinkedList<>();
Queue<String> pathQueue = new LinkedList<>();
queue.add(root);
pathQueue.add(String.valueOf(root.val));
while (!queue.isEmpty()) {
root = queue.poll();
String s = pathQueue.poll();
if (root.left == null && root.right == null) {
res.add(s);
} else {
if (root.left != null) {
queue.add(root.left);
pathQueue.add(s + "->" + root.left.val);
}
if (root.right != null) {
queue.add(root.right);
pathQueue.add(s + "->" + root.right.val);
}
}
}
return res;
}
