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算法的问题请转到回溯算法标签