摘要

【面试必刷101】系列blog目的在于总结面试必刷101中有意思、可能在面试中会被考到的习题。总结通用性的解题方法，针对特殊的习题总结思路。既是写给自己复习使用，也希望与大家交流。
【面试必刷101】递归/回溯算法总结I（十分钟理解回溯算法）
【面试必刷101】递归/回溯算法总结II（十分钟刷爆回溯算法题）
【面试必刷101】链表

1 基础知识

1.1 二叉数的遍历

很简单，先序、中序与后序的遍历分别对应着根先被访问，中间被访问和最后被访问。层次遍历更好理解了，就一层一层遍历呗。
1、先（根）序遍历

    void pre_order (TreeNode node) {
        if (node == null) return;
        process(node);
        pre_order(node.left);
        pre_order(node.right);
    }
1
2
3
4
5
6

2、中（根）序遍历

    void pre_order (TreeNode node) {
        if (node == null) return;
        pre_order(node.left);
        process(node);
        pre_order(node.right);
    }
1
2
3
4
5
6

3、后（根）序遍历

    void pre_order (TreeNode node) {
        if (node == null) return;
        pre_order(node.left);
        pre_order(node.right);
        process(node);
    }
1
2
3
4
5
6

4、层次遍历
层次遍历用到了队列。一端出，一段入，看代码比较好理解。
举个例子：

    public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
        // write code here
        if (root == null) return null;
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        
        Deque<TreeNode> dq = new LinkedList<>();
        dq.addLast(root);
        
        while (dq.size() > 0) {
            int size = dq.size();
            ArrayList<Integer> lay = new ArrayList<>();
            while (size > 0) {
                TreeNode tmp = dq.removeFirst();
                size--;
                lay.add(tmp.val);
                if (tmp.left != null) {
                    dq.addLast(tmp.left);
                }
                if (tmp.right != null) {
                    dq.addLast(tmp.right);
                }
            }
            res.add(lay);
        }
        return res;
    }
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

这里用到了哪个知识点呢？如果单纯用队列，可以输出层次遍历的结果，那么怎么判断是同一层的呢？这里使用了一个trick：使用一个变量size来记录该层的个数。这是咋实现的呢？上一层的全部出队列了，留下的全是下一层的，因此size=dq.size()。这种trick在下面的几道题都用得上。

2 面试必刷习题

2.1 按之字形打印二叉树

BM27 按之字形顺序打印二叉树

这题的小trick就是使用了一个tag记录层数，通过判断层数决定是否要进行翻转。思路与层次遍历无异。

import java.util.*;
import java.util.ArrayList;

public class Solution {
    public ArrayList<ArrayList<Integer> > Print(TreeNode root) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        if (root == null) return res;
        
        Deque<TreeNode> dq = new LinkedList<>();
        dq.addLast(root);
        int tag = 0;
        while (dq.size() > 0) {
            tag++; // 表示层数
            int size = dq.size();
            ArrayList<Integer> lay = new ArrayList<>();
            while (size > 0) {
                TreeNode tmp = dq.removeFirst();
                size--;
                lay.add(tmp.val);
                if (tmp.left != null) {
                    dq.addLast(tmp.left);
                }
                if (tmp.right != null) {
                    dq.addLast(tmp.right);
                }
            }
            if (tag % 2 == 0) {
                // 表示偶数层,原地翻转
                Collections.reverse(lay);
            }
            res.add(lay);
        }
        return res;
    }
}
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

2.2 二叉搜索树与双向链表

二叉搜索树与双向链表

这个题还是超有意思。首先给我的感受是：原来二叉树可以直接改成一个双向链表，好像两者之间没有啥隔阂，连数据结构都不需要变。

言归正传，题目一看就知道需要用中序遍历，但是需要记录上一个节点是啥，然后题目要求返回第一个节点，这个也是需要记录的。然后就是左右指针的修改了。具体的思路很简单，注释写的很清楚了。上代码：

import java.util.*;
// 显然是一个中序遍历
public class Solution {
    // 需要记录两个值：函数返回的第一个节点的指针，上一个节点
    TreeNode root = null;
    TreeNode pre = null;
    // 为啥这里pre可以作为一个全局变量而不是函数传进去呢？因为pre是由left节点遍历之后才可以得到的，当前节点不知道pre是哪个，因此使用全局变量进行维护pre
    // 怎么记录root呢？不仅需要“当前节点不为空，左节点为空”的条件，好需要判断是不是第一次出现，第一次出现的判别方式是root是否被赋值了，这个还需要记一下。
    public TreeNode Convert(TreeNode pRootOfTree) {
        if (pRootOfTree == null) return null;
        if (pRootOfTree.left == null && root == null) {
            root = pRootOfTree;
        }
        
        Convert(pRootOfTree.left);
        // 仅仅考虑左边的：pre与pRootOfTree之间的关联。构建两条指针。
        pRootOfTree.left = pre;
        if (pre != null) {
            pre.right = pRootOfTree;
        }
        pre = pRootOfTree;
        
        Convert(pRootOfTree.right);
        return root;
    }
}
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

2.3 对称二叉树

对称二叉树

这题还是一个小trick，使用一个两个参数的遍历来做。

public class Solution {
    boolean isSymmetrical(TreeNode pRoot) {
        if (pRoot == null) return true;
        return isSym(pRoot.left, pRoot.right);
    }
    
    boolean isSym (TreeNode left, TreeNode right) {
        if (left == null && right == null) return true;
        if (left == null || right == null || left.val != right.val) return false;
        return isSym(left.left, right.right) && isSym(left.right, right.left);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

2.4 合并二叉树

合并二叉树

这题的精髓在于递归，虽然题目简单，但是这写法值得学习。递归需要明白自己在做啥。谁都知道在当前节点需要将两数求和，但是递归结束的条件是啥？下一步怎么递归下去？返回值是啥？这个也是要时刻去想的。

import java.util.*;

public class Solution {
    public TreeNode mergeTrees (TreeNode t1, TreeNode t2) {
        // write code here
        if (t1 == null) return t2;
        if (t2 == null) return t1;
        t1.val += t2.val;
        t1.left = mergeTrees (t1.left, t2.left);
        t1.right = mergeTrees (t1.right, t2.right);
        return t1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

2.5 二叉树的镜像

二叉树的镜像
这题的精髓在于每个节点的左右节点都要镜像，直接递归就好了。

public class Solution {
    //每个节点左右节点都镜像，这就很好做了
    public TreeNode Mirror (TreeNode pRoot) {
        if (pRoot == null) return null;
        TreeNode tmp = pRoot.left;
        pRoot.left = pRoot.right;
        pRoot.right = tmp;
        
        Mirror (pRoot.left);
        Mirror (pRoot.right);
        
        return pRoot;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

2.6 判断是不是二叉搜索树

判断是不是二叉搜索树

这道题首先要抓住二叉搜索树的特点，左边的最大小于中间节点，中间节点小于右边的最小。

其实思路比较简单，左中右的话，一定是中序遍历，但是怎么记录左边的最大呢？用一个pre记录上一个节点，其实不用那么花里胡哨的，可以直接理解为中序遍历的结果中，上一个节点的值一定小于下一个节点的值，否则返回false。

import java.util.*;

public class Solution {
    // 一看就知道是中序遍历，然后用pre记录前一个节点
    TreeNode pre = null;
    public boolean isValidBST (TreeNode root) {
        // write code here
        if (root == null) return true;
        
        if (!isValidBST(root.left)) return false;
        
        // 左边的最大小于中间节点
        if (pre != null && pre.val > root.val) return false;
        pre = root;
        
        if (!isValidBST(root.right)) return false;
        
        return true;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

2.7 判断是不是完全二叉树

判断是不是完全二叉树

完全二叉树特点：除去第h层之外，其他的节点达到最大个数。涉及到层数，想到的就是层序遍历。这题判断size是没有用的，因为需要满足的条件是最后一层的全部在左边。因此采用一个tag来判断是不是上一层出现或者节点之前出现了null的节点，出现了就不是完全二叉树了。这题与层次遍历的一点点差别在于将null也插入到队列中了。

import java.util.*;

public class Solution {
    public boolean isCompleteTree (TreeNode root) {
        // 完全二叉树就是层次遍历，注意一定要出现在左边，而且是首次
        Deque<TreeNode> dq = new LinkedList<>();
        
        boolean tag = false;
        dq.addLast(root);
        while (dq.size() > 0) {
            int size = dq.size();
            while (size > 0) {
                size --;
                TreeNode tmp = dq.pollFirst();
                if (tmp == null) {
                    tag = true;
                    continue;
                }
                if (tag) {
                    return false;
                }
                dq.addLast(tmp.left);
                dq.addLast(tmp.right);
            }
        }
        return true;
    }
}
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

2.8 输出二叉树的右视图

题目链接：输出二叉树的右视图

这题的难点在于先要根据先序遍历和中序遍历进行二叉树重建，然后再输出右视图；

二叉树重建有两种写法，其实核心方案就是根据先序遍历当前i位置划分中序遍历，得到哪些是在左边，哪些节点是在右边，然后迭代处理就好了。右视图比较简单，层次遍历就可以得到结果。

import java.util.*;

public class Solution {
    Map<Integer, Integer> map;
    int idx = 0;
    public int[] solve (int[] xianxu, int[] zhongxu) {
        // write code here
        map = new HashMap<>();
        for (int i = 0; i < xianxu.length; i++) {
            map.put(zhongxu[i], i);
        }
        TreeNode root = rebuildTree(xianxu, zhongxu, 0, xianxu.length - 1);
        // 输出右视图其实就是层次遍历的最后一个值罢了。
        Deque<TreeNode> dq = new LinkedList<>();
        dq.addLast(root);
        ArrayList<Integer> arrlist = new ArrayList<>();
        while (dq.size() > 0) {
            int size = dq.size();
            while (size > 0) {
                size--;
                TreeNode tmpNode = dq.pollFirst();
                if (size == 0) {
                    arrlist.add(tmpNode.val);
                }
                if (tmpNode.left != null) {
                    dq.addLast(tmpNode.left);
                }
                if (tmpNode.right != null) {
                    dq.addLast(tmpNode.right);
                }
            }
        }
        int[] res = new int[arrlist.size()];
        for (int i = 0; i < res.length; i++) {
            res[i] = arrlist.get(i);
        }
        return res;
    }
    
    TreeNode rebuildTree (int[] xianxu, int[] zhongxu, int s, int e) {
        if (xianxu.length == 0) return null;
        if (idx >= xianxu.length || s > e) return null;
        TreeNode root = new TreeNode(xianxu[idx]);
        int t = map.get(xianxu[idx]);
        idx ++;
        root.left = rebuildTree(xianxu, zhongxu, s, t - 1);
        root.right = rebuildTree(xianxu, zhongxu, t + 1, e);
        return root;
    }
}
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

3 知识点总结

其实做完上面八道题，整个二叉树还是围绕“遍历+递归”两个知识点进行。

• 之字形打印二叉树：层序遍历
• 二叉搜索树与双向链表：中序遍历
• 对称二叉树：先序遍历（左右节点的）
• 合并二叉树：先序遍历（两个树的）
• 二叉树的镜像：先序遍历
• 判断是不是二叉搜索树：先序遍历
• 判断是不是完全二叉树：层序遍历
• 输出二叉树的右视图：二叉树重建 + 层序遍历

递归的话还是自己详细跟一下程序是怎么运行的，看看全局变量和函数变量是怎么赋值的。然后需要跳出来，因为递归是将大问题化为小问题解决的， 跳出变量的赋值，看当前的问题是怎么解决的。这种跳入、跳出的思维还是要多写才能够体会出来。

4 总结

大道至简，砥砺前行。