关于二叉树，最重要的莫过于遍历了。
- 深度优先遍历和层次遍历（广度优先遍历）
- 递归实现和迭代实现
- 前序遍历、后序遍历以及中序遍历
那么一共有（3+2）*2=10种模版之多。先看前序遍历。
前序遍历
递归实现
这是最简单的前序遍历的递归实现
1
2
3
4
5
6
7
| void dfs（TreeNode* root）{
if(root==nullptr) reutrn root;
dfs(root->left);
dfs(root->right);
return;
}
|
迭代实现
借助栈stack实现前序遍历。
1
2
3
4
5
6
7
8
9
10
11
12
13
| int[] preorderTraversal(TreeNode root){
if(root == null) return root;
List<Integer> ans = new ArrayList<Integer>();
Stack<TreeNode> stk = new Stack<>();
stk.push(root);
while(!stk.isEmpty()){
TreeNode cur = stk.pop();
ans.add(cur.val);
if(cur.right!=null) stk.push(cur.right);
if(cur.left!=null) stk.push(cur.left);
}
return ans;
}
|
注意点：
- 空节点不入栈（若空节点入栈，则出栈时需要加以校验）
- 入栈顺序（入栈顺序与前序遍历相反）
层次遍历
递归实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
public List<List<Integer>> ans = new ArrayList<>();
public void bfs(TreeNode root, int depth){
if(root==null) return ;
if(ans.size() == depth)
ans.add(new ArrayList<Integer>());
ans[depth].add(root.val);
bfs(root.left, 1+depth);
bfs(root.right, 1+depth);
}
bfs(root, 0);
|
注意点：
- 答案的存储方式：一层存一个List，所以是个二维数组；
- 层次遍历需要传入深度信息，利用二维数组来判断当前遍历到的层数。
迭代实现
迭代实现借助队列，由于队列先进先出，可以记录一层的数量。
（1）实现一
1
2
3
4
5
6
7
8
9
10
11
12
13
| public int[] levelOrder(TreeNode root){
if(root==null) return;
List<Integer> ans = new ArrayList<>();
Queue<TreeNode> que = new ArrayList<>();
que.offer(root);
while(!que.isEmpty()){
TreeNode node = que.poll();
ans.add(node.val);
if(node.left!=null) que.offer(node.left);
if(node.right!=null) que.offer(node.right);
}
return ans.toArray()；
}
|
注意点：
- 空节点不入队或节点出队判空
- 可以不用二维数组处理答案
（2）实现二
巧妙的利用队列的性质，for 长度遍历。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
public List<List<Integer>> ans = new ArrayList<>();
public int[] levelOrder(TreeNode root){
if(root==null) return;
List<Integer> ans = new ArrayList<>();
Queue<TreeNode> que = new ArrayList<>();
que.offer(root);
while(!que.isEmpty()){
int count = que.size();
for(int i=0; i<count;++i){
TreeNode node = que.poll();
ans.add(node.val);
if(node.left!=null) que.offer(node.left);
if(node.right!=null) que.offer(node.right);
}
}
return ans-to-int-array；
}
|
迭代实现中序遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| vector<int> inorderTraversal(TreeNode* root) {
vector<int> result;
stack<TreeNode*> st;
if (root != NULL) st.push(root);
while (!st.empty()) {
TreeNode* node = st.top();
st.pop();
if (node != NULL) {
if (node->right) st.push(node->right);
st.push(node);
st.push(NULL);
if (node->left) st.push(node->left);
} else {
node = st.top();
st.pop();
result.push_back(node->val);
}
}
return result;
}
|
注意处理节点的技巧是：中节点后添加nullptr标志。
在首次遇到节点时，并不首先处理它，而是将它加入栈中，紧跟其后添加一个nullptr标志。而当我们再次取到nullptr时，它提醒我们该处理一个结点了。
这个技巧的思想是：标记，直到遍历完才处理数据。
题目练习
每种题目都尝试递归和迭代两种写法！迭代可以实现层序遍历和深度优先遍历（前中后序遍历）。
BFS
填充每个节点的下一个右侧指针
https://leetcode.cn/problems/populating-next-right-pointers-in-each-node/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public Node connect(Node root) {
if(root==null) return root;
Queue<Node> que = new ArrayDeque<>();
que.offer(root);
while(!que.isEmpty()){
int count = que.size();
for(int i=0; i<count; ++i){
Node node = que.poll();
if(i!=count-1) node.next = que.peek();
if(node.left!=null) que.offer(node.left);
if(node.right!=null) que.offer(node.right);
}
}
return root;
}
}
|
层次遍历的应用。
二叉树的最小深度
https://leetcode.cn/problems/minimum-depth-of-binary-tree/description/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| public int minDepth(TreeNode root) {
int ans = 0;
if(root == null) return ans;
Queue<TreeNode> que = new ArrayDeque<>();
que.offer(root);
boolean stop = false;
while(!que.isEmpty()){
int size = que.size();
++ans;
for(int i=0; i<size; ++i){
TreeNode cur = que.poll();
if(cur.left==null && cur.right==null)
stop = true;
if(cur.left != null)
que.offer(cur.left);
if(cur.right != null)
que.offer(cur.right);
}
if(stop) break;
}
return ans;
}
|
层次遍历-碰到叶子节点就返回。实际是bfs的应用。
左下角的值
https://leetcode.cn/problems/find-bottom-left-tree-value/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public int findBottomLeftValue(TreeNode root) {
if(root==null) return 0;
Queue<TreeNode> que = new ArrayDeque<>();
que.offer(root);
int ans =-1;
while(!que.isEmpty()){
int size = que.size();
for(int i=0; i<size; ++i){
TreeNode node = que.poll();
if(i<1) ans = node.val;
if(node.left!=null) que.offer(node.left);
if(node.right!=null) que.offer(node.right);
}
}
return ans;
}
}
|
什么是左下角？数最深一层的第一个节点！还是层次遍历。
DFS
相同的树
https://leetcode.cn/problems/same-tree/
1
2
3
4
5
6
7
| class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
if(p==null || q==null) return q==p ? true:false;
if(p.val != q.val) return false;
return isSameTree(p.left, q.left)&&isSameTree(p.right, q.right);
}
}
|
翻转二叉树
https://leetcode.cn/problems/invert-binary-tree/description/
1
2
3
4
5
6
7
8
9
10
11
| class Solution {
public TreeNode invertTree(TreeNode root) {
if(root==null) return root;
TreeNode rl = invertTree(root.left);
TreeNode rr = invertTree(root.right);
root.left = rr;
root.right = rl;
return root;
}
}
|
这道题考的其实是递归的思想。
左叶子之和
https://leetcode.cn/problems/sum-of-left-leaves/
注意左叶子的定义，需要通过父节点来判断。
1
2
3
4
5
6
7
8
| class Solution {
public int sumOfLeftLeaves(TreeNode root) {
if(root==null) return 0;
if(root.left!=null && root.left.left==null && root.left.right==null)
return root.left.val+sumOfLeftLeaves(root.right)+sumOfLeftLeaves(root.left);
return sumOfLeftLeaves(root.left)+sumOfLeftLeaves(root.right);
}
}
|
1
2
3
| if (node->left != NULL && node->left->left == NULL && node->left->right == NULL) {
左叶子节点处理逻辑
}
|
路径总和
https://leetcode.cn/problems/path-sum/
1
2
3
4
5
6
7
8
9
10
| class Solution {
public boolean dfs(TreeNode root, int targetSum){
if(root==null) return false;
if(root.left==null&&root.right==null&&targetSum==root.val) return true;
return dfs(root.left, targetSum-root.val) || dfs(root.right, targetSum-root.val);
}
public boolean hasPathSum(TreeNode root, int targetSum) {
return dfs(root, targetSum);
}
}
|
给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
路径开始节点固定：根结点。那么很容易利用递归整棵树。
路径总和2
https://leetcode.cn/problems/path-sum-ii/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
List<List<Integer>> ans = new ArrayList<>();
List<Integer> path = new ArrayList<>();
public void dfs(TreeNode root, int targetSum){
if(root==null) return;
path.add(root.val);
if(root.left==null&&root.right==null&&targetSum==root.val){
ans.add(new ArrayList<Integer>(path));
}
dfs(root.left, targetSum-root.val);
dfs(root.right, targetSum-root.val);
path.remove(path.size()-1);
}
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
dfs(root, targetSum);
return ans;
}
}
|
回溯法来收集路径上的值。
路径总和3
https://leetcode.cn/problems/sum-root-to-leaf-numbers/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
int ans=0;
List<Integer> path = new ArrayList<>();
public void dfs(TreeNode root, int cur){
if(root==null) return;
path.add(root.val);
int next_cur = cur*10 +root.val;
if(root.left==null&&root.right==null){
ans +=next_cur;
}
dfs(root.left, next_cur);
dfs(root.right, next_cur);
path.remove(path.size()-1);
}
public int sumNumbers(TreeNode root) {
dfs(root, 0);
return ans;
}
|
二叉树的所有路径
https://leetcode.cn/problems/binary-tree-paths/
（1）字符串普通拼接
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public List<String> ans = new ArrayList<>();
public void dfs(TreeNode root, String str){
if(root==null) return;
if(root!=null && root.left==null && root.right==null){
ans.add(str+String.valueOf(root.val));
return;
}
str = str + String.valueOf(root.val) + "->";
dfs(root.left, str);
dfs(root.right, str);
}
public List<String> binaryTreePaths(TreeNode root) {
dfs(root, "");
return ans;
}
}
|
（2）java优化写法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public List<String> res = new ArrayList<>();
public List<String> binaryTreePaths(TreeNode root) {
if(root==null) return res;
dfs(root,new StringBuilder());
return res;
}
public void dfs(TreeNode r, StringBuilder s){
if(r==null) return;
s.append(r.val);
if(r.left==null && r.right==null){
res.add(s.toString());
}
dfs(r.left,new StringBuilder(s).append("->"));
dfs(r.right,new StringBuilder(s).append("->"));
}
}
|
二叉树的直径
https://leetcode.cn/problems/diameter-of-binary-tree/description/
（1）暴力DFS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
Map<TreeNode, Integer> map = new HashMap<>();
public int dfs(TreeNode root){
if(root==null) return 0;
int left = 1 + dfs(root.left);
int right = 1 + dfs(root.right);
int ret = Math.max(left, right);
if(!map.containsKey(root))
map.put(root, ret);
return ret;
}
public int diameterOfBinaryTree(TreeNode root) {
if(root==null) return 0;
int now = dfs(root.left) + dfs(root.right);
int l = diameterOfBinaryTree(root.left);
int r = diameterOfBinaryTree(root.right);
now = Math.max(now, l);
now = Math.max(now, r);
return now;
}
}
|
二叉树的直径：二叉树中从一个节点到另一个节点的最长边数和。
从一个节点到另外一个节点，肯定是会经过过某棵树的根，以这个根将路径分为两部分，左子树的高度和右子树的高度。
定义树的高度：从根节点到叶子节点的最长路径边的个数，叶子节点的高度为0。
由此得到递归公式：
1
| 根节点为root的二叉树的直径 = max(root->left的直径，root->right的直径，2 + root->left高度+root->right高度)
|
实际上操作时，我们定义新高度值为高度值都加1，即下面情况
1
| 根节点为root的二叉树的直径 = max(root->left的直径，root->right的直径，1+root->left高度 + 1+root->right高度)
|
（2）优化DFS
我们利用DFS求高度，遍历了每个节点。同时为了求解答案，我们还需要遍历每个节点的直径。能够将这两个遍历合二为一呢？
答案是可以！在求高度时，我们得出了左右子树的高度。求当前root节点高度的操作是取max，而求直径的操作是加和，两者互不干预。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
int ans = 0;
public int dfs(TreeNode root){
if(root==null) return 0;
int left = dfs(root.left);
int right = dfs(root.right);
int depth = 1 + Math.max(left, right);
ans = Math.max(ans, left+right);
return depth;
}
public int diameterOfBinaryTree(TreeNode root) {
dfs(root);
return ans;
}
}
|
构建二叉树
进阶题目
其他题目
扁平化嵌套列表
https://leetcode.cn/problems/flatten-nested-list-iterator/description/
（1）暴力遍历
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
| public class NestedIterator implements Iterator<Integer> {
private Iterator<Integer> myIt;
private List<Integer> myList = new ArrayList<>();
public void traverse(List<NestedInteger> nestedList){
if(nestedList.isEmpty()) return;
for(NestedInteger node: nestedList){
if(node.isInteger())
myList.add(node.getInteger());
else
traverse(node.getList());
}
}
public NestedIterator(List<NestedInteger> nestedList) {
traverse(nestedList);
myIt = myList.iterator();
}
@Override
public Integer next() {
return myIt.next();
}
@Override
public boolean hasNext() {
return myIt.hasNext();
}
}
|
其实是N叉树的深度优先遍历。结合迭代器。
（2）优化
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
public class NestedIterator implements Iterator<Integer> {
private LinkedList<NestedInteger> list;
public NestedIterator(List<NestedInteger> nestedList) {
list = new LinkedList<>(nestedList);
}
@Override
public Integer next() {
return list.remove(0).getInteger();
}
@Override
public boolean hasNext() {
while(!list.isEmpty() && !list.get(0).isInteger()){
List<NestedInteger> nodeList = list.remove(0).getList();
for(int i=nodeList.size()-1; i>=0; --i){
list.addFirst(nodeList.get(i));
}
}
return !list.isEmpty();
}
}
|
优化：上述解法将所有叶子节点值存入一个List中，当输入规模非常大时，上述计算会很慢，占用内存。一般迭代器是“惰性”求值的，也就是说，你要一个值，我算一个值，而不是一次将所有结果都求出来。
1
2
3
4
| res = []
while iterator.hasNext()
append iterator.next() to the end of res
return res
|
在调用next前会有hasNext来判断是否已经达到尾巴。那么hashNext做的事就是判断list的第一个元素是否是列表，如果是列表就将其拆开。注意列表是嵌套的，所以要用while循环。
滑动谜题
https://leetcode.cn/problems/sliding-puzzle/description/
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
| class Solution {
int ans = 0;
public boolean isCompleted(int[][] board){
for(int i=0; i<3;++i){
if(board[0][i] != (i+1)) return false;
}
if(board[1][0]!=4) return false;
if(board[1][1]!=5) return false;
return true;
}
public int slidingPuzzle(int[][] array) {
Set<String> set = new HashSet<>();
Queue<int[][]> que = new ArrayDeque<>();
que.offer(array);
while(!que.isEmpty()){
int size = que.size();
for(int i=0; i<size; ++i){
int[][] board = que.poll();
if(isCompleted(boarad)) return ans;
int m=0,n=0;
for(int k=0; k<6; ++k){
if(board[k/3][k%3]==0){
m = k/3;
n = k%3;
break;
}
}
if(m == 1){
int[][] tmp = new int[2][3];
tmp[0] = Arrays.copyOf(board[0], 3);
tmp[1] = Arrays.copyOf(board[1], 3);
tmp[m][n] = tmp[m-1][n];
tmp[m-1][n] = 0;
if(!set.contains(Arrays.deepToString(tmp))){
que.offer(tmp);
set.add(Arrays.deepToString(tmp));
}
}
if(m == 0){
int[][] tmp = new int[2][3];
tmp[0] = Arrays.copyOf(board[0], 3);
tmp[1] = Arrays.copyOf(board[1], 3);
tmp[m][n] = tmp[m+1][n];
tmp[m+1][n] = 0;
if(!set.contains(Arrays.deepToString(tmp))){
que.offer(tmp);
set.add(Arrays.deepToString(tmp));
}
}
if(n==1 || n==2){
int[][] tmp = new int[2][3];
tmp[0] = Arrays.copyOf(board[0], 3);
tmp[1] = Arrays.copyOf(board[1], 3);
tmp[m][n] = tmp[m][n-1];
tmp[m][n-1] = 0;
if(!set.contains(Arrays.deepToString(tmp))){
que.offer(tmp);
set.add(Arrays.deepToString(tmp));
}
}
if(n==0 || n==1){
int[][] tmp = new int[2][3];
tmp[0] = Arrays.copyOf(board[0], 3);
tmp[1] = Arrays.copyOf(board[1], 3);
tmp[m][n] = tmp[m][n+1];
tmp[m][n+1] = 0;
if(!set.contains(Arrays.deepToString(tmp))){
que.offer(tmp);
set.add(Arrays.deepToString(tmp));
}
}
}
ans++;
}
return -1;
}
}
|
求最短路径：广度优先搜索+回溯法
注意点：
- 广搜的实现-队列
- 层次广搜的特定实现方式：for-que.size()， 特别注意要先得到size，否则队列的size会变
- 为了避免无穷尽的搜索，用set记录走过局面。（这里局面用数组toString的方式记录）