【每日算法Day 27】二叉树基础2
Wallace Xu 2020-06-27 树
基于二叉树遍历的应用，涉及状态、路径的保存与传递。
在前面的学习中，我们掌握了二叉树的递归与迭代遍历方法，结合遍历方法能做很多事。例如，编写一个函数来检验两个二叉树是否相同 (opens new window)：
public boolean isSameTree(TreeNode p, TreeNode q) {
if(p==null && q==null) return true;
if(p==null || q==null) return false;
if(p.val==q.val) return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
return false;
}
1
2
3
4
5
6
2
3
4
5
6
还可以来检验他们是否互为镜像 (opens new window)：
public boolean isSymmetric(TreeNode p,TreeNode q) {
if(p==null && q==null) return true;
if(p==null || q==null) return false;
if(p.val==q.val) return isSymmetric(p.left,q.right)&&isSymmetric(p.right,q.left);
return false;
}
//当然要检验一棵树本身是否为镜像二叉树也是可以的
public boolean isSymmetric(TreeNode root) {
return isSymmetric(root, root);
}
1
2
3
4
5
6
7
8
9
10
11
2
3
4
5
6
7
8
9
10
11
还可以用来翻转一棵二叉树 (opens new window)：
public TreeNode invertTree(TreeNode root) {
if(root!=null){
TreeNode temp=root.left;
root.left=invertTree(root.right);
root.right=invertTree(temp);
return root;
}
return null;
}
1
2
3
4
5
6
7
8
9
2
3
4
5
6
7
8
9
上面这些问题都类似于广度优先遍历，有使用队列来辅助解决的迭代写法。在《剑指Offer》一书中也有详细的讲解。
# 257. 二叉树的所有路径 (opens new window)
# 题目描述
给定一个二叉树，返回所有从根节点到叶子节点的路径。
# 示例
输入:
1
/ \
2 3
\
5
输出: ["1->2->5", "1->3"]
解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3
1
2
3
4
5
6
7
8
9
10
11
2
3
4
5
6
7
8
9
10
11
# 解题思路
这一题如果使用递归，需要另写一个函数来传递遍历到当前节点时形成的字符串，把该节点的值追加到字符串中，如果当前节点是叶子节点则把该字符串放入容器中。
递归解法DFS
public List<String> binaryTreePaths(TreeNode root) {
List<String> list = new ArrayList<>();
binaryTreePaths(root,list,"");
return list;
}
private void binaryTreePaths(TreeNode current, List<String> list, String string) {
if (current != null) {
String s=string+current.val;
if (current.left == null && current.right == null) {
list.add(s);
} else {
binaryTreePaths(current.left,list,s+"->");
binaryTreePaths(current.right,list,s+"->");
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
由于这题只是要求遍历到所有的叶子节点，并且在遍历过程中就需要把根节点加到字符串中，所以选用前序遍历和层次遍历都是可以的。对应地要使用非递归方法，则DFS+栈或BFS+队列都可以。
# LeetCode 112. 路径总和 (opens new window)
# 题目描述
给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
# 示例
给定如下二叉树，以及目标和 sum = 22，
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。
1
2
3
4
5
6
7
8
9
10
2
3
4
5
6
7
8
9
10
# 解题思路
采用前序遍历或层次遍历，一旦发现遍历到叶子节点，且当前路径的和等于目标值就返回true。否则，将目标值减去当前节点的值，返回两个叶子节点中是否满足新的目标值。
public boolean hasPathSum(TreeNode root, int sum) {
if (root != null) {
if (root.left==null&&root.right==null&&root.val==sum) return true;
return hasPathSum(root.left,sum-root.val)||hasPathSum(root.right,sum-root.val);
}
return false;
}
1
2
3
4
5
6
7
2
3
4
5
6
7
虽然递归写起来很方便，我还写了这题的非递归解：
//使用栈与DFS实现非递归解，实际慢一些
public boolean hasPathSum2(TreeNode root, int sum) {
if (root==null) return false;
Deque<TreeNode> nodeStack = new LinkedList<>();
Deque<Integer> sumStack = new LinkedList<>();
nodeStack.push(root);
sumStack.push(0);
while (!nodeStack.isEmpty()){
TreeNode current=nodeStack.pop();
int currentSum=sumStack.pop()+current.val;
if (current.left == null && current.right == null && currentSum == sum) {
return true;
} else {
if (current.right != null) {
nodeStack.push(current.right);
sumStack.push(currentSum);
}
if (current.left != null) {
nodeStack.push(current.left);
sumStack.push(currentSum);
}
}
}
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
25
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# 113. 路径总和 II (opens new window)
# 题目描述
给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
# 示例
给定如下二叉树，以及目标和 sum = 22，
5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
返回:
[
[5,4,11,2],
[5,8,4,5]
]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 解题思路
在前面两题的基础上，只需要在遍历时，传递一个容器保存当前遍历过的路径，遇到叶子节点并且满足目标时把路径保存到容器中。
public List<List<Integer>> pathSum(TreeNode root, int sum) {
List<List<Integer>> resultSet=new LinkedList<>();
if (root != null) {
List<Integer> currentPath= new LinkedList<>();
traversal(resultSet,currentPath,root,sum);
}
return resultSet;
}
private void traversal(List<List<Integer>> resultSet,List<Integer> currentPath,TreeNode current,int sum){
if (current != null) {
List<Integer> path = new LinkedList<>(currentPath);
path.add(current.val);
if (current.left == null && current.right == null && current.val == sum) {
resultSet.add(path);
} else {
traversal(resultSet,path,current.left,sum-current.val);
traversal(resultSet,path,current.right,sum-current.val);
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
注意每次向下传递当前的路径集合后，子节点拿到该集合需要创建一个新的集合来放入自己，否则由于Java的值传递，会导致最终加入到结果集的结果都相同。
其实还可以在回溯的时候剪枝，在确定添加结果时在创建新的List，这样不用每一步都创建新的List，省去了许多不必要的操作。