112. 路径总和
力扣题目链接(opens new window)
给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
说明: 叶子节点是指没有子节点的节点。
示例: 给定如下二叉树，以及目标和 sum = 22，
返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。
思路
这道题我们要遍历从根节点到叶子节点的的路径看看总和是不是目标和。
递归
可以使用深度优先遍历的方式（本题前中后序都可以，无所谓，因为中节点也没有处理逻辑）来遍历二叉树
- 确定递归函数的参数和返回类型
参数：需要二叉树的根节点，还需要一个计数器，这个计数器用来计算二叉树的一条边之和是否正好是目标和，计数器为int型。
再来看返回值，递归函数什么时候需要返回值？什么时候不需要返回值？这里总结如下三点：
- 如果需要搜索整棵二叉树且不用处理递归返回值，递归函数就不要返回值。（这种情况就是本文下半部分介绍的113.路径总和ii）
- 如果需要搜索整棵二叉树且需要处理递归返回值，递归函数就需要返回值。 （这种情况我们在236. 二叉树的最近公共祖先 (opens new window)中介绍）
- 如果要搜索其中一条符合条件的路径，那么递归一定需要返回值，因为遇到符合条件的路径了就要及时返回。（本题的情况）
而本题我们要找一条符合条件的路径，所以递归函数需要返回值，及时返回，那么返回类型是什么呢？
如图所示：
图中可以看出，遍历的路线，并不要遍历整棵树，所以递归函数需要返回值，可以用bool类型表示。
所以代码如下：
1
| bool traversal(treenode* cur, int count) // 注意函数的返回类型
|
- 确定终止条件
首先计数器如何统计这一条路径的和呢？
不要去累加然后判断是否等于目标和，那么代码比较麻烦，可以用递减，让计数器count初始为目标和，然后每次减去遍历路径节点上的数值。
如果最后count == 0，同时到了叶子节点的话，说明找到了目标和。
如果遍历到了叶子节点，count不为0，就是没找到。
递归终止条件代码如下：
1
2
| if (!cur->left && !cur->right && count == 0) return true; // 遇到叶子节点，并且计数为0
if (!cur->left && !cur->right) return false; // 遇到叶子节点而没有找到合适的边，直接返回
|
- 确定单层递归的逻辑
因为终止条件是判断叶子节点，所以递归的过程中就不要让空节点进入递归了。
递归函数是有返回值的，如果递归函数返回true，说明找到了合适的路径，应该立刻返回。
代码如下：
1
2
3
4
5
6
7
8
9
| if (cur->left) {
if (traversal(cur->left, count - cur->left->val)) return true;
}
if (cur->right) {
if (traversal(cur->right, count - cur->right->val)) return true;
}
return false;
|
以上代码中是包含着回溯的，没有回溯，如何后撤重新找另一条路径呢。
回溯隐藏在traversal(cur->left, count - cur->left->val)这里， 因为把count - cur->left->val 直接作为参数传进去，函数结束，count的数值没有改变。
为了把回溯的过程体现出来，可以改为如下代码：
1
2
3
4
5
6
7
8
9
10
11
| if (cur->left) {
count -= cur->left->val;
if (traversal(cur->left, count)) return true;
count += cur->left->val;
}
if (cur->right) {
count -= cur->right->val;
if (traversal(cur->right, count)) return true;
count += cur->right->val;
}
return false;
|
整体代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| public boolean hasPathSum(TreeNode root, int targetSum) {
if(root == null) return false;
boolean res = Isfind(root,targetSum);
return res;
}
public boolean Isfind(TreeNode root,int count) {
if(root.left == null && root.right == null) {
count -= root.val;
if(count == 0) return true;
}
if(root.left != null) {
return Isfind(root.left,count - root.val);
}
if(root.right != null) {
return Isfind(root.right,count - root.val);
}
return false;
}
|
迭代法：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public boolean hasPathSum(TreeNode root, int targetSum) {
if(root == null) return false;
Deque<TreeNode> que0 = new LinkedList<>();
Deque<Integer> que1 = new LinkedList<>();
que0.push(root);
que1.push(root.val);
while(!que0.isEmpty()) {
TreeNode node = que0.pop();
int sum = que1.pop();
if(node.left == null && node.right == null && sum == targeSum) return true;
if(node.left!=null) {
que0.push(node.left);
que1.push(sum+node.left.val);
}
if(node.right != null) {
que0.push(node.right);
que1.push(sum+node.right.val);
}
}
return false;
}
}
|
