二叉树的遍历

先序遍历

递归版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public void preorder(Node head) {

    // 递归终止条件
    if (head == null) {
        return;
    }
    // 访问树节点
    Visit(head);

    // 遍历左子树
    preorder(head.left);

    // 遍历右子树
    preorder(head.right);
}

非递归版本

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 void preOrder(Node head) {
    
    if (head != null) {
        // 定义辅助栈
        Stack<Node> stack = new Stack<>();
        // 根节点入栈
        stack.add(head);
        
        // 先访问根节点，再访问左子树，然后访问右子树
        while (!stack.isEmpty()) {
            // 弹出栈顶一个节点  
            head = stack.pop();
            Visit(head);
            // 先入栈该节点的右孩子 （栈的先进后出性质）
            if (head.right != null) {
                stack.push(head.right);
            }
            // 再入栈该节点的左孩子
            if (head.left != null) {
                stack.push(head.left);
            }
        }
    }
}

中序遍历

递归版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public void inorder(Node head) {

    // 递归终止条件
    if (head == null) {
        return;
    }

    // 先访问左子树
    inorder(head.left);
    
    // 再访问根节点
    // Visit(head);

    // 最后访问右子树
    inorder(head.right);
}

非递归版本

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
public List<Node> inorder(Node head) {
    List<Node> ans = new ArrayList<>();
    Stack<Node> stack = new Stack<>();
    
    if (head == null) {
        return ans;
    }
    
    while (!stack.isEmpty() || head != null) {
        // 一直往左分支走
        while (head != null) {
            stack.push(head);
            head = head.left;
        }
        
        if (!stack.isEmpty()) {
            head = stack.pop();
            ans.add(head); // Visit(head)
            // 转向右分支
            head = head.right;
        }
        
    }
    return ans;
}

后序遍历

递归版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public void postorder(Node head) {
    
    // 递归终止条件
    if (head == null) {
        return;
    }
    
    // 访问左子树
    postorder(head.left);
    
    // 访问右子树
    postorder(head.right);
    
    // 访问根节点
    //Visit(head);
}

非递归版本

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
// 逆先序
// 先序遍历非递归版本进栈顺序是：根右左
// 后序遍历非递归版本采用双栈，进栈顺序是：根左右
public void postorder(Node head) {

    if (head != null) {
        // 输入栈
        Stack<Node> in = new Stack<>();
        // 输出栈
        Stack<Node> out = new Stack<>();

        // 将根节点放入输入栈
        in.push(head);

        while (!in.isEmpty()) {

            // 从输入栈取出栈顶元素放入输出栈中
            head = in.pop();
            out.push(head);

            // 先 左
            if (head.left != null) {
                in.push(head.left);
            }

            // 后 右
            if (head.right != null) {
                in.push(head.right);
            }
        }

        // 输出
        while (!out.isEmpty()) {
            out.pop();
        }
    }
}

二叉树宽度

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
// 经典层次遍历模型
public int getBinaryTreeWidth(Node head) {

    int maxsize = 100;
    // 定义哨兵
    Node sentinel;
    // 定义队列
    Node[] que = new Node[maxsize]; // MaxSize根据实际题目而定
    // 定义指针
    int front = 0, rear = 0;
    // 记录当前最大宽度
    int max = 0;
    // 定义当前层次节点数
    int count = 0;
    // 记录当前层次最后一个节点
    int last = 1;

    // 根节点入队
    rear = (rear + 1) % maxsize;
    que[rear] = head;

    while (front != rear) {
        // 出队一个节点
        front = (front + 1) % maxsize;
        sentinel = que[front];

        // 记录当前节点
        count++;

        // 哨兵节点的左孩子入队
        if (sentinel.left != null) {
            rear = (rear +1) % maxsize;
            que[rear] = sentinel.left;
        }

        // 哨兵节点的右孩子入队
        if (sentinel.right != null) {
            rear = (rear +1) % maxsize;
            que[rear] = sentinel.right;
        }

        // 更新层次
        if (front == last) {
            // last指向下一层层次最后一个节点
            last = rear;
            // 更新最大节点数
            max = count > max ? count : max;
            // 重置节点数
            count = 0;
        }
    }
    return max;
}

二叉搜索树

判断方式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 boolean isBST(Node head) {
    // 空树符合要求
    if (head == null) {
        return false;
    }

    List<Node> inList = new LinkedList<>();

    process(head, inList);

    int pre = Integer.MIN_VALUE;

    // 如果中序遍历不是递增的，不是二叉搜索树
    for (Node node: inList) {
        if (pre >= node.val) {
            return false;
        }
        pre = node.val;
    }
    return true;
}

public void process(Node node, List<Node> inList) {
    if (node == null) {
        return;
    }
    process(node.left, inList);
    inList.add(node);
    process(node.right, inList);
}

判断方式2 常规递归检查

算法思想

判断是否为BST，主要是看BST性质：对于其下的任意一颗子树，其左孩子节点的值小于其根节点的值，其根节点的值小于其右孩子的值，因此用递归解决

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
int prev = Integer.MIN_VALUE;

public boolean isBST(Node head) {
    // 空树是一个BST
    if (head == null) {
        return true;
    }
    // 首先检查左子树，需要返回一个结果
    boolean isLeftBST = isBST(head.left);  

    // 如果左子树不符合要求，则返回false
    if (!isLeftBST) {  // (左子树是否满足)
        return false;
    }
    // 检查当前节点与它左孩子大小
    if (head.val <= prev) { // (左子树与当前根节点关系是否满足)
        // 不满足条件
        return false;
    } else {
        // 更新prev，准备检查右子树
        prev = head.val;
    }
    // 检查其右子树
    return isBST(head.right); // (右子树是否满足)
}

判断方式3 树型DP套路

树型DP使用场景

如果题目求解目标 $S$ 规则，其求解流程定成以每一个节点为头结点的子树在 $S$ 下的每个答案，并且最终答案一定在其中

算法思想

  • 判断BST，以X为根节点的BST满足：左子树为BST，右子树为BST，对应左子树的 $maxX$
  • 因此左子树需要的信息 （1.左子树是否为BST 2.左子树的Max）
  • 因此右子树需要的信息 (1.右子树是否为BST 2.右子树的Min)

Step1 以某个节点X为头结点的子树中，分析答案的可能性，并且可能性是以X的左子树、X的右子树和X整棵树的角度考虑的

  1. X左子树是否为BST
  2. X右子树是否为BST
  3. 以X为根节点的树是否为BST

Step2 根据可能性，列出需要的信息

  1. 左子树是否为BST
  2. 左子树的最大值
  3. 右子树是否为BST
  4. 右子树的最小值

Step3 合并第二步信息，对左子树和右子树提出同样要求，写出信息结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class ReturnData {
    
    // 该子树是否为BST
    public boolean isBST;
    // 该子树中最小值
    public int min;
    // 该子树中最大值
    public int max;

    public ReturnData(boolean isBST, int min, int max) {
        this.isBST = isBST;
        this.min = min;
        this.max = max;
    }

}

Step4 设计递归函数，递归函数处理以X为头节点的情况下的答案，包括设计递归的basecase，默认直接得到左子树和右子树的所有信息，以及把可能性做出整合

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
public ReturnData process(Node head) {

    // 如果头节点为空，返回null
    if (head == null) {
        return null;
    }

    // 递归检查左子树
    ReturnData leftData = process(head.left);
    // 递归检查右子树
    ReturnData rightData = process(head.right);

    /*核心代码*/

    // 记录右子树的最小值（实际是整颗子树中的最大最小值都取出来）
    int min = head.val;
    // 记录左子树的最大值（实际是整颗子树中的最大最小值都取出来）
    int max = head.val;

    // 求出左孩子最小值与最大值
    if (leftData != null) {
        min = Math.min(min, leftData.min);
        max = Math.max(max, leftData.max);
    }
    // 求出右孩子最小值与最大值
    if (rightData != null) {
        min = Math.min(min, rightData.min);
        max = Math.max(max, rightData.max);
    }

    boolean isBST = true;

    // 当左孩子不是BST或左孩子中的最大值>=head时，返回false
    if (leftData != null && (!leftData.isBST || leftData.max >= head.val)) {
        isBST = false;
    }
    // 当右孩子不是BST或右孩子中的最小值<=head时，返回false
    if (rightData != null && (!rightData.isBST || head.val >= rightData.min)) {
        isBST = false;
    }

    // 返回整合后的信息结构
    return new ReturnData(isBST, max, min);
}
1
2
3
public boolean isBST(Node head) {
    return process(head).isBST;
}

完全二叉树

算法思想

  • 层次遍历二叉树

  • 如果当前节点有右孩子节点，但没有左孩子节点，直接返回 false

  • 如果当前节点并不是全有左右孩子，那么之后的节点必须为叶子节点，否则返回false

  • 遍历过程不返回false，遍历结束后返回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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
public boolean isCBT(Node head) {
    // 空树符合要求
    if (head == null) {
        return true;
    }

    LinkedList<Node> queue = new LinkedList<>();

    // 定义叶子判断标记
    boolean leaf = false;

    // 定义双指针
    Node lchild = null;
    Node rchild = null;

    // 头节点入队
    queue.add(head);

    while (!queue.isEmpty()) {
        // 弹出队首节点
        head = queue.poll();
        lchild = head.left;
        rchild = head.right;

        // 1. 开启叶子判断
        // 2. 如果有右孩子但无左孩子，则返回false
        if (leaf && (lchild != null || rchild!= null) || (lchild == null && rchild != null)) {
            return false;
        }
        
        // 左孩子入队
        if (lchild != null) {
            queue.add(lchild);
        }
        
        // 右孩子入队
        if (rchild != null) {
            queue.add(rchild);
        }
        
        // 第一次遇到不是拥有两个孩子的节点，则开启叶子判断
        if (lchild == null || rchild == null) {
            leaf = true;
        }
    }
    return true;
}

平衡二叉树

Step1 以 X 为头节点的子树中，分析答案的可能性。以X的左子树、X的右子树和X整棵树角度分析可能性

  • X的左子树是否平衡

  • X的右子树是否平衡

  • X为头结点的左右子树高度差

  • 上述满足后，则平衡

Step2 根据可能性列出需要的信息，本题是要知道左子树是否平衡，右子树是否平衡，以及高度信息

Step3 整合信息

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 信息结构
public class ReturnData {

    // 是否平衡
    public boolean isBalanced;

    // 高度
    public int height;

    public ReturnData(boolean isBalanced, int height) {
        
        this.isBalanced = isBalanced;
        this.height = height
    }

}

Step4 设计递归函数，处理以X为头节点的情况的答案，包括 base case，左右子树信息，以及可能性整合，返回信息结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 递归函数
public ReturnData process(Node x) {

    // 空树满足条件
    if (x == null) {
        return new ReturnData(true, 0);
    }

    // 递归检查左子树
    ReturnData leftData = process(x.left);

    // 递归检查右子树
    ReturnData rightData = process(x.right);

    // 树的高度
    int height = Math.max(leftData.height, rightData.height) + 1;

    // 平衡性
    boolean isBalanced = leftData.isBalanced && rightData.isBalanced && Math.abs(leftData.height - rightData.height) < 2;
    
    // 返回整合的信息
    return new ReturnData(isBalanced, height);
}

调用函数

1
2
3
4
// 调用
public boolean isBalanced(Node head) {
    return process(head).isBalanced;
}

满二叉树

树形dp

Step1 以x为头节点的子树中，分析答案的可能性，以x的左子树、x的右子树和x整棵树角度去分析可能性

Step2 根据可能性列出需要的信息，本题是要知道节点数量和树的高度

Step3 整合信息

1
2
3
4
5
6
7
8
9
10
11
12
// 整合信息
public class ReturnData{
    // 树的高度
    public int height;
    // 节点数
    public int nodes;

    public ReturnData(int height, int nodes) {
        this.height = height;
        this.nodes = nodes;
    }
}

Step4 设计递归函数，处理以x为头节点的情况的答案，包括base case，左右子树信息，以及可能性整合，返回信息结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 递归函数
public ReturnData process(Node x) {
    // 空树返回信息
    if (x == null) {
        return new ReturnData(0, 0);
    }

    // 返回左子树的信息
    ReturnData leftData = process(x.left);

    // 返回右子树的信息
    ReturnData rightData = process(x.right);

    // 求以x为根结点的树的高度
    int height = Math.max(leftData.height, rightData.height) + 1;

    // 求以x为根结点的树的数量
    int nodes = leftData.nodes + rightData.nodes + 1;

    // 返回信息结构
    return new ReturnData(height, nodes);
}

最终调用

1
2
3
4
5
6
7
8
9
public boolean isFBT(Node head) {
	// 空树情况
    if (head == null) {
        return true;
    }
    // 返回信息
    ReturnData data = process(head);
    return data.nodes == (1 << data.height - 1);
}

找一个节点中序遍历下的后继节点

1
2
3
4
5
6
7
8
9
10
public class Node {
    public int value;
    public Node left;
    public Node right;
    public Node parent;

    public Node(int data) {
        this.value = data;
    }
}

情况1 node有右子树

如果node有右子树,那么后继节点就是右子树上最左边的节点

情况2 node没有右子树

如果node没有右子树, 先看node是不是node父节点的左孩子节点

  • 如果node是其父节点的左孩子节点, 那么此时node的父节点是node的后继节点

  • 如果node是其父节点的右孩子节点, 就向上寻找node的后继节点, 假设向上移动到的节点为s,s的父节点是p, 如果发现s是p的左孩子, 那么节点p便是node的后继节点,否则就一直向上移动

情况3

如果在情况2中一直寻找，都移动到空节点时还是没有发现node的后继节点，说明node根本不存在后继节点

getLeftMost

1
2
3
4
5
6
7
8
9
10
11
12
// 找到一棵二叉树的最左边的节点
public Node getLeftMost(Node node) {
    if (node == null) {

        return node;
    }
    while (node.left != null) {
        node = node.left;
    }
    return node;

}

getNextNode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public Node getNextNode(Node node) {
    // 如果节点为空
    if (node == null) {
        return node;
    }

    // 情况1 如果node有右子树，那么node的后继节点就是该右子树上最左边的节点
    if (node.right != null) {
        return getLeftMost(node.right);
    } else {
        // 如果node没有右子树，西安看node是不是node父节点的左孩子节点
        Node parent = node.parent;
        // 如果是右孩子节点，就向上寻找node的后继节点
        // 假设向上移动到的节点记为s，s的父节点记为p
        // 如果发现s是p的左孩子节点，那么节点p就是node的后继节点，否则就一直向上移动
        while (parent != null && parent.left != node) {
            node = parent;
            parent = node.parent;
        }
        // 如果是左孩子节点，那么此时node的父亲节点就是node的后继节点
        return parent;
    }
}

序列化问题

给出一个定义：

二叉树被记录成文件的过程叫序列化，通过文件内容重建原来的二叉树叫反序列化。给定一颗二叉树的头节点head，已知二叉树节点类型为32位整数，设计序列化和反序列化的方案

先序遍历

序列化方法

1
2
3
4
5
6
7
8
9
public String serialByPre(Node head) {
    if (head == null) {
        return "#!";
    }
    String res = head.value + "!";
    res += serialByPre(head.left);
    res += serialByPre(head.right);
    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
// 先序遍历反序列化
public Node reconPreString(String preStr) {
    String[] values = preStr.split("!");

    Queue<String> queue = new LinkedList<>();

    // 将字符串切割后装入队列
    for (String val : queue) {
        queue.offer(val);
    }

    return reconPreOrder(queue);
}

public Node reconPreOrder(Queue<String> queue) {
    String value = queue.poll();
    if (value.equals("#")) {
        return null;
    }

    Node head = new Node(Integer.valueOf(value));
    head.left = reconPreOrder(queue);
    head.right = reconPreOrder(queue);
    return head;
}

层次遍历

序列化方法

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
// 层次遍历序列化
public String serialByLevel(Node head) {


    if (head == null) {
        return "#!";
    }

    String res = head.val + "!";
    Queue<Node> queue = new LinkedList<>();
    queue.offer(head);

    while (!queue.isEmpty()) {
        head = queue.poll();

        if (head.left != null) {
            res += head.left.val + "!:";
            queue.offer(head.left);
        } else {
            res += "#!";
        }
        if (head.right != null) {
            res += head.right.val + "!";
            queue.offer(head.right);
        } else {
            res += "#!";
        }
    }

    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
36
// 层次遍历反序列化
public Node reconByLevelString(String levelStr) {

    String[] values = levelStr.split("!");
    int index = 0;
    Node head = generateNodeByString(values[index++]);
    Queue<Node> queue = new LinkedList<>();

    if (head != null) {
        queue.offer(head);
    }
    Node node = null;
    while (!queue.isEmpty()) {

        node = queue.poll();
        // 设置左孩子
        node.left = generateNodeByString(values[index++]);
        // 设置右孩子
        node.right = generateNodeByString(values[index++]);
        if (node.left != null) {
            queue.offer(node.left);
        }
        if (node.right != null) {
            queue.offer(node.right);
        }
    }
    return head;

}

public Node generateNodeByString(String str) {
    if (str.equals("#")) {
        return null;
    }
    return new Node(Integer.valueOf(str));
}

最近公共祖先

给定一颗二叉树的头节点head，以及这棵树中的两个节点o1和o2，请返回o1和o2的最近公共祖先

原始问题

算法思想

后序遍历二叉树，当前节点记为cur，假设处理cur左子树返回节点为left，处理右子树时返回节点为right

如果发现cur等于null，或者o1、o2，则返回cur
如果left和right都为空，说明cur整棵子树没有发现过o1或o2，返回null
如果left和right都不为空，说明左子树发现过o1或o2，右子树也发现过o1或o2，说明o1向上与o2向上的过程中，首次在cur相遇，返回cur
如果left和right有一个为空，另一个不为空，假设不为空的那个记为node，此时node要么是o1或o2的一个，要么是o1和o2的最近公共祖先，直接返回node

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public Node lowestAncestor(Node head, Node o1, Node o2) {
    // 如果发现cur等于null，或者o1、o2，则返回cur
    if (head == null || head == o1 || head == o2) {
        return head;
    }
    // 检查左子树
    Node left = lowestAncestor(head.left, o1, o2);
    // 检查右子树
    Node right = lowestAncestor(head.right, o1, o2);

    // 如果left和right都不为空，说明左子树发现过o1或o2，右子树也发现过o1或o2，
    // 说明o1向上与o2向上的过程中，首次在cur相遇，返回cur
    if (left != null && right != null) {
        return head;
    }

    // 左右两棵树并不都有返回值
    // 如果left和right有一个为空，另一个不为空，假设不为空的那个记为node，此时node要么是o1或o2的一个，要么是o1和o2的最近公共祖先，直接返回node
    // 如果left和right都为空，说明cur整棵子树没有发现过o1或o2，返回null
    return left != null ? left : right;
}

进阶问题

如果查询操作十分频繁，请想办法让单条查询的查询时间减少。

结构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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
public class Record {
    // 定义哈希表表示 <子结点, 父结点>
    private HashMap<Node, Node> map;

    public Record(Node head) {
        map = new HashMap<>();
        // 如果没有父结点
        if (head != null) {
            map.put(head, null);
        }
        setMap(head);
    }

    // 构造map
    public void setMap(Node x) {
        // 如果结点为空，则返回
        if (x == null) {
            return;
        }
        // 如果左孩子存在，设置左孩子的父结点
        if (x.left != null) {
            map.put(x.left, x);
        }
        // 如果右孩子存在，设置右孩子的父结点
        if (x.right != null) {
            map.put(x.right, x);
        }
        // 递归调用左子树
        setMap(x.left);
        // 递归调用右子树
        setMap(x.right);
    }

    public Node query(Node o1, Node o2) {
        // 存储包括o1结点在内的所有o1结点的祖先结点
        // path表示从结点o1到头结点这条路径上所有结点的和
        HashSet<Node> path = new HashSet<>();

        // 填充path
        while (map.containsKey(o1)) {
            path.add(o1);
            //获取o1的父节点
            o1 = map.get(o1);
        }
        // 遍历o2的所有父结点与path中进行核对，找出最近公共祖先
        while (!path.contains(o2)) {
            o2 = map.get(o2);
        }
        return o2;
    }
}

复杂度分析

结构1建立记录的过程时间复杂度为 $O(N)$、额外空间复杂度为 $O(N)$，进行查询操作时，时间复杂度为 $O(h)$，其中，$h$ 为二叉树的高度。

结构2：优化结构

直接建立任意两个子结点之间的最近公共祖先记录，加速查询

建立过程：

1.对二叉树中的每棵子树（一共N棵）都进行步骤2
2.假设子树的头结点为h

  • h所有后代结点和h结点的最近公共祖先都是h，并记录下来。
  • h的左子树的每个结点和h右子树的每个结点的最近公共祖先都是h，并记录下来。
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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
public class Record {
    // 建立任意两个结点之间最近公共祖先的哈希表
    private HashMap<Node, HashMap<Node, Node>> map;

    public Record(Node head) {
        map = new HashMap<>();
        initMap(head);
        setMap(head);
    }

    public void initMap(Node head) {
        // 如果结点为空，退出
        if (head == null) {
            return;
        }
        map.put(head, new HashMap<>());

        initMap(head.left);
        initMap(head.right);
    }

    public void setMap(Node head) {
        // 如果结点为空
        if (head == null) {
            return;
        }
        // 根结点下的所有节点构成的哈希表的值部分初始化<h,h>
        // <n, <h, h>>
        headRecord(head.left, head);
        headRecord(head.right, head);

        subRecord(head);

        setMap(head.left);
        setMap(head.right);
    }

    // 将以n为根结点的所有子树的结点和h结点的最近公共祖先标为h
    public void headRecord(Node n, Node h) {
        if (n == null) {
            return;
        }
        // <n, <h,h>>
        map.get(n).put(h, h);

        headRecord(n.left, h);
        headRecord(n.right, h);
    }

    // 将head为根结点的整棵树的最近公共祖先标head
    public void subRecord(Node head) {
        // 头结点为空，退出
        if (head == null) {
            return;
        }
        preLeft(head.left, head.right, head);

        subRecord(head.left);
        subRecord(head.right);
    }

    // 将h左子树的每个结点的最近公共祖先标为h
    public void preLeft(Node l, Node r, Node h) {
        // h的左孩子r为空
        if (l == null) {
            return;
        }
        preRight(l, r, h);

        preLeft(l.left, r, h);
        preLeft(l.right, r, h);
    }

    // 将h右子树的每个结点的最近公共祖先标为h
    public void preRight(Node l, Node r, Node h) {
        // h的右孩子r为空
        if (r == null) {
            return;
        }
        // <l,<r,h>>
        // 构建以l为键，<r,h>为值得哈希表，表示r的祖先为h
        map.get(l).put(r, h);

        preRight(l, r.left, h);
        preRight(l, r.right, h);
    }

    public Node query(Node o1, Node o2) {
        if (o1 == o2) {
            return o1;
        }
        if (map.containsKey(o1)) {
            return map.get(o1).get(o2);
        }
        if (map.containsKey(o2)) {
            return map.get(o2).get(o1);
        }
        return null;
    }
}