LeetCode 112/113. 路径总和，两道同类树形路径问题，熟悉DFS、回溯解法。
112. 路径总和#
https://leetcode.cn/problems/path-sum/
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。
叶子节点 是指没有子节点的节点。
DFS#
树形遍历，我习惯用DFS处理。我们只需逐个节点遍历、求和检查即可。
同时为了避免传递多余的targetSum变量，在每次进入dfs，我们都可以实时更新值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
static class Recursion {
public boolean hasPathSum(TreeNode root, int targetSum) {
return dfs(root, targetSum);
}
private boolean dfs(TreeNode node, int targetSum) {
if (node == null) {
return false;
}
if (node.left == null && node.right == null && node.val == targetSum) {
return true;
}
return dfs(node.left, targetSum - node.val) || dfs(node.right, targetSum - node.val);
}
}
|
复杂度分析#
n表示树节点个数
整个过程遍历一次完整树，时间复杂度O(n)。
正常情况下空间占用为递归调用栈，即树的高度，空间复杂度O(logn)。
树形退化为链表时，空间占用为n个元素，空间复杂度O(n)。
113. 路径总和 II#
https://leetcode.cn/problems/path-sum-ii/
给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
叶子节点 是指没有子节点的节点。
DFS回溯#
在112的基础上，113题要求返回符合和条件的路径，因此我们除了最外层的ansList，肯定也需要内部的一个集合来记录、回溯路径。
我们用回溯的做法来遍历、求解。
我们使用Deque<Integer> innerQueue记录子节点的处理状态，同时node.left!=null时，回溯相应添加状态。
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
|
public class PathSumII {
List<List<Integer>> ans;
Deque<Integer> innerQueue;
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
ans = new ArrayList<>();
innerQueue = new ArrayDeque<>();
dfs(root, targetSum);
return ans;
}
private void dfs(TreeNode node, int targetSum) {
if (node == null) {
return;
}
innerQueue.offerLast(node.val);
if (node.left == null && node.right == null && node.val == targetSum) {
ans.add(new ArrayList<>(innerQueue));
return;
}
dfs(node.left, targetSum - node.val);
if (node.left != null) {
innerQueue.pollLast();
}
dfs(node.right, targetSum - node.val);
if (node.right != null) {
innerQueue.pollLast();
}
}
}
|
复杂度分析#
n表示树节点个数
整个过程遍历一次完整树，时间复杂度O(n)。
树形退化为链表时，空间占用为n个元素，空间复杂度O(n)。