文章目录
- [257. 二叉树的所有路径](https://leetcode-cn.com/problems/binary-tree-paths/)
- [112. 路径总和](https://leetcode-cn.com/problems/path-sum/)
- [113. 路径总和 II](https://leetcode-cn.com/problems/path-sum-ii/)
- [437. 路径总和 III](https://leetcode-cn.com/problems/path-sum-iii/)
- [124. 二叉树中的最大路径和](https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/)
- 详细解析
- 后续遍历
257. 二叉树的所有路径
难度简单514
给定一个二叉树，返回所有从根节点到叶子节点的路径。
说明: 叶子节点是指没有子节点的节点。
示例:
输入:
1
/ \
2 3
\
5
输出: ["1->2->5", "1->3"]
解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3
public List<String> binaryTreePaths(TreeNode root) {
List<String> res = new ArrayList<>();
dfs(root, "", res);
return res;
}
private void dfs(TreeNode root, String path, List<String> res) {
if (root == null) {
return;
}
StringBuffer string = new StringBuffer(path);
string.append(root.val);
if (root.left == null && root.right == null) {
res.add(string.toString());
}
string.append("->");
dfs(root.left, string.toString(), res);
dfs(root.right, string.toString(), res);
}112. 路径总和
难度简单593
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum ，判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。
叶子节点 是指没有子节点的节点。
示例 1：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出：true
递归
/**
* 递归
*
* @param root
* @param targetSum
* @return
*/
public boolean hasPathSum(TreeNode root, int targetSum) {
if (root == null) {
return false;
}
if (root.left == null && root.right == null && targetSum - root.val == 0) {
return true;
}
return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val);
}
非递归
public boolean hasPathSum1(TreeNode root, int targetSum) {
if (root == null) {
return false;
}
Deque<TreeNode> stack = new ArrayDeque<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode cur = stack.pop();//出栈
//累加到叶子节点之后，结果等于sum，说明存在这样的一条路径
if (cur.left == null && cur.right == null) {
if (cur.val == targetSum)
return true;
}
//右子节点累加，然后入栈
if (cur.right != null) {
cur.right.val = cur.val + cur.right.val;
stack.push(cur.right);
}
//左子节点累加，然后入栈
if (cur.left != null) {
cur.left.val = cur.val + cur.left.val;
stack.push(cur.left);
}
}
return false;
}113. 路径总和 II
难度中等499
给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
叶子节点 是指没有子节点的节点。
示例 1：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：[[5,4,11,2],[5,8,4,5]]
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
List<List<Integer>> result = new ArrayList<>();
dfs(root, targetSum, new ArrayList<>(), result);
return result;
}
private void dfs(TreeNode root, int targetSum,
List<Integer> list, List<List<Integer>> result) {
//如果节点为空直接返回
if (root == null)
return;
//把当前节点值加入到list中
list.add(new Integer(root.val));
//如果到达叶子节点，就不能往下走了，直接return
if (root.left == null && root.right == null) {
//如果到达叶子节点，并且sum等于叶子节点的值，说明我们找到了一组，
//要把它放到result中
if (targetSum == root.val)
result.add(new ArrayList(list));
//注意别忘了把最后加入的结点值给移除掉，因为下一步直接return了，
//不会再走最后一行的remove了，所以这里在rerurn之前提前把最后
//一个结点的值给remove掉。
list.remove(list.size() - 1);
//到叶子节点之后直接返回，因为在往下就走不动了
return;
}
//如果没到达叶子节点，就继续从他的左右两个子节点往下找，注意到
//下一步的时候，sum值要减去当前节点的值
dfs(root.left, targetSum - root.val, list, result);
dfs(root.right, targetSum - root.val, list, result);
//我们要理解递归的本质，当递归往下传递的时候他最后还是会往回走，
//我们把这个值使用完之后还要把它给移除，这就是回溯
list.remove(list.size() - 1);
}437. 路径总和 III
难度中等876
给定一个二叉树，它的每个结点都存放着一个整数值。
找出路径和等于给定数值的路径总数。
路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
二叉树不超过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
public int pathSum(TreeNode root, int sum) {
if (root == null) {
return 0;
}
int res = 0;
// 遍历每个节点，并且将每一个节点都过一遍 countPath()，将所有节点的有效路径加起来
res += countPath(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
return res;
}
/*
计算从某一个节点出发一共能有多少条路径
*/
public int countPath(TreeNode root, int sum) {
if (root == null) {
return 0;
}
int count = 0;
if (root.val == sum) {
++count;
}
int leftCount = countPath(root.left, sum - root.val);
int rightCount = countPath(root.right, sum - root.val);
count += leftCount + rightCount;
return count;
}124. 二叉树中的最大路径和
难度困难1072收藏分享切换为英文接收动态反馈
路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root ，返回其 最大路径和 。
示例 1：
输入：root = [1,2,3]
输出：6
解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6
详细解析
后续遍历
为什么是「后序遍历」
深度优先遍历就是从根结点开始在树中转一圈，最后回到根结点。我们采用后序遍历计算结果的方式，表现为：
从叶子结点开始，一层一层向上传递信息，最后在根结点汇总结果。
为什么是「后序遍历」呢？
- 因为二叉树从子结点到父结点只会有一条路径；
- 而从根结点到子节点至多会有两条路径。
「后序遍历」相当于 先求得两个子问题的结果，再根据两个子问题的结果得到当前规模更大的子问题的结果，这是「分而治之」的思想。
题目问的结果在求解子问题的过程中得到
我们对状态的定义规定了只来自左右子树的一边，在后序遍历的时候，左右子树的结果都求得的情况下，当前结点就可以把左右两棵子树的求解结果进行综合，就是题目要求的 经过某个结点 的最大路径和。
下面给出「参考代码」，我们把需要注意的地方作为注释写在代码中，「树形 DP」与的状态设计与状态转移是隐含在递归方法里的，这一点请大家留意。
大家可以先理解代码，代码之后有一个具体的例子，展示了代码是如何执行，并计算题目要求的结果的。
class Solution {
int res;
public int maxPathSum(TreeNode root) {
res = Integer.MIN_VALUE;
dfs(root);
return res;
}
private int dfs(TreeNode root) {
if (root == null) {
return 0;
}
int leftSum = Math.max(0, dfs(root.left));
int rightSum = Math.max(0, dfs(root.right));
res = Math.max(res, root.val + leftSum + rightSum);
return root.val + Math.max(leftSum, rightSum);
}
}总结
首先是理解题意，对「路径」的定义的理解非常关键，直接决定了递归函数（也就是状态设计）为什么规定了「路径」只能来自其中一个子树。
- 然后是求解这一类问题的思想：
- 后序遍历：一层一层向上传递；
无后效性：把不确定的因素固定下来，以便分类讨论。
如果大家做过「力扣」第 53 题：最大子序和 就会发现，当前问题（「力扣」第 124 题） 其实是这道问题的在树上的版本。重点再说一遍：
- 路径的定义；
- 后序遍历；
- 动态规划的无后效性。