二叉树的路径总和问题
LeetCode上有一系列的 二叉树路径总和 的问题, 如图
这篇文章中我们按照 I, II, III的顺序依次解决此类题目
给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
说明: 叶子节点是指没有子节点的节点。
示例:
给定如下二叉树，以及目标和 sum = 22，
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/path-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题解：
这道题思路比较简单， 无非就是 dfs深度遍历二叉树, 到叶子节点时，如果和为给定的target， 则return true。 否则选择另一条路继续遍历
这样看起来，貌似有点 回溯算法 的意思？
下边，我们用递归 / 非递归两种实现方式解决此题。
思路一 ： 递归
深度优先遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
// 递归
static boolean hasPathSumRecursive(TreeNode root, int sum) {
// 根节点为空，直接返回false
if (root == null) return false;
// 遍历到 root 时， 将 sum的值 减去 root.val
sum -= root.val;
// 此时，如果root为叶子节点， 返回 true， 否则返回false
if (root.left == null && root.right == null) return sum == 0;
// 继续分别遍历 root的左右子节点
// 两个中，有一个为 true 则返回true。 都为false， 则返回false
return hasPathSumRecursive(root.left,sum) || hasPathSumRecursive(root.right,sum);
}
|
思路二：迭代
深度优先遍历
使用栈 迭代 前序遍历二叉树
推导过程如下图 :
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
// 迭代
static boolean hasPathSum(TreeNode root, int sum) {
if (root == null) return false;
// 节点栈
Stack<TreeNode>stack = new Stack<>();
stack.push(root);
// 数字栈
Stack<Integer> numStack = new Stack<>();
numStack.push(sum - root.val);
// 当栈不为空时 循环
while (!stack.isEmpty()){
// 节点栈 取出节点
TreeNode node = stack.pop();
// 数字栈 取出数字
int num = numStack.pop();
// 当节点为跟节点， 且 数字为 0时。 符合条件，return true
if (node.left == null && node.right == null && num == 0) return true;
// 将 节点的 右/左子节点 以及 num与子节点的差值 分别入栈
if (node.right != null) {
stack.push(node.right);
numStack.push(num - node.right.val);
}
if (node.left != null){
stack.push(node.left);
numStack.push(num - node.left.val);
}
}
// 遍历完一整棵树，一直没有叶子节点，且 数字为0的情况， 则返回false
return false;
}
|
给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
说明: 叶子节点是指没有子节点的节点。
示例:
给定如下二叉树，以及目标和 sum = 22，
5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
返回:
[
[5,4,11,2],
[5,8,4,5]
]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/path-sum-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题解：
前序遍历 + 回溯算法
- 首先使用前序遍历， 前序遍历是第一次访问到相应节点， 就进行操作的一种遍历方式， 回溯算法的题目基本都是采用先序遍历的方式。
- 从 root 节点开始， 当访问到一个节点时， 将节点的 value 记录在 path 中
- 因为要记录所有经过的节点， 所以 path 是要在递归过程中逐层的转递的， 所以当访问完某一个节点后，要将该节点的 value 从 path 中删除。
- path 中的元素， 通过上面两个步骤的操作， nums 中的元素始终都是代表从跟，到当前节点路径的所有元素
当到达任意叶子节点， 则计算 sum(nums) == target 如果相等， 则放入全局的 res 数组中
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
// 结果数组
LinkedList<List<Integer>> res = new LinkedList<>();
// 路径
LinkedList<Integer> path = new LinkedList<>();
public void dfs(TreeNode node, int sum){
if (node == null) return;
path.add(node.val);
sum -= node.val;
if (sum == 0 && node.left == null && node.right == null)
// 注意这里需要 new 一个path，防止后续path的修改中，影响已添加的结果.../
res.add(new LinkedList<>(path));
dfs(node.left, sum);
dfs(node.right, sum);
// 回溯
path.removeLast();
}
public List<List<Integer>> pathSum(TreeNode root, int sum) {
dfs(root, sum);
return res;
}
|
