Leetcode日记：112&113.路径之和与DFSvs回溯
路径走到头，深度搜索优。路径回头走，回溯其中由
112路径之和I
112问题
Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.
Note: A leaf is a node with no children.
Example:
Given the below binary tree and sum = 22,
1
2
3
4
5
6
7
| 5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
|
return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.
112问题分析
Leetcode上有很多关于树的问题，而关于树的问题很多需要DFS，这个我们下面会详细讲到，总之问题很明确，判断这个树有没有一条从头到尾的路径，这条路径上所有元素之和等于目标值。
112代码
下面是我写的复杂版，还要多出一个全局变量，明显可改进。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
boolean isFirst = true;
public boolean hasPathSum(TreeNode root, int sum) {
if(root==null){
return false;
}
if(root.left==null&&root.right==null){
if(root.val==sum)
return true;
else
return false;
}
if(root.left==null){
return hasPathSum(root.right, sum - oot.val);
}
if(root.right==null)
return hasPathSum(root.left, sum - root.val);
return hasPathSum(root.left, sum - root.val)||hasPathSum(root.right, sum - root.val);
}
}
|
下面是大神给出的简洁方案
1
2
3
4
5
6
7
8
9
| public class Solution {
public boolean hasPathSum(TreeNode root, int sum) {
if(root == null)
return false;
if(root.left == null && root.right == null && sum - root.val == 0)
return true;
return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
}
}
|
113路径之和II
113问题
Given a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals the given sum.
Note: A leaf is a node with no children.
Example:
Given the below binary tree and sum = 22,
1
2
3
4
5
6
7
| 5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
|
Return:
1
2
3
4
| [
[5,4,11,2],
[5,8,4,5]
]
|
113问题分析
和112差不多，但是这次让我们找出所有符合要求的路径
113代码
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 List<List<Integer>> pathSum(TreeNode root, int sum) {
List<List<Integer>> result = new LinkedList();
List<Integer> sub = new LinkedList();
backtrack(result, sub, root, sum);
return result;
}
private void backtrack(List<List<Integer>> result, List<Integer> sub, TreeNode root, int sum) {
if (root == null) {
return;
}
sub.add(root.val);
if (root.left == null && root.right == null) {
if (root.val == sum) {
result.add(new LinkedList(sub));
}
sub.remove(sub.size() - 1);
return;
}
backtrack(result, sub, root.left, sum - root.val);
backtrack(result, sub, root.right, sum - root.val);
sub.remove(sub.size() - 1);
}
}
|
DFSvs回溯
DFS还是回溯？
第一道题，仔细分析他的算法流程，就会发现，他和之前我们介绍过的回溯一样，先一路走到黑，走不动了，就返回上一个路口，走另一条路。
而有趣的是，第二道题的代码，看着熟不熟悉，对，他的代码形式像极了之前的回溯。
那么说了那么半天，什么是DFS？
DFS，Depth first search，即深度优先遍历（或者说深度优先搜索），当我们学习完回溯再回过头来卡看DFS时，发现他俩极其类似。
区别在于：DFS从不剪枝。
具体地说，回溯可以看作一种更通用的DFS，在某些情况下，可以放弃一些路径的深度遍历；而对于DFS而言，对于它适用的数据结构树和图来讲，都是需要从头遍历到尾的，不能有一丝遗漏，这便是这二者之间的区别。
问题分析
之所以这两道题的标签是DFS， 是因为这道题说的是从头到尾的路径，既然是从头到尾，肯定不能有一丝遗漏。我们只需要在迭代中判断结点是否已经到低就可以，对于112，如果是则判断路径之和符不符合，如果没到底继续迭代；对于113，如果已经到底则判断路径之和符不符合，如果符合，将得到的数组添加到已有库中，如果不符合回退数组，如果没到底，则继续迭代。
更多DFS算法
更多关于DFS算法的问题请转到回溯算法标签
