【数据结构与算法】二叉树刷题笔记

1. 二叉树

节点结构：

public class Node<V> {
    V value;
    Node<V> left;
    Node<V> right;
}
复制代码

2. 二叉树的遍历

2.1 递归序

有一个如下构造的二叉树：

我们使用递归的方式遍历如上二叉树：

public static void traversal(Node root) {
    if (root == null) {
        return ;
    }
    System.out.println(root.value);
    traversal(root.left);
    System.out.println(root.value);
    traversal(root.right);
    System.out.println(root.value);
}
复制代码

执行结果为：[ 1, 2, 4, 4, 4, 2, 5, 5, 5, 2, 1, 3, 6, 6, 6, 3, 7, 7, 7, 3, 1 ]

该结果就是二叉树的递归序。

由递归序发现，每一个节点的value都被连续或者不连续输出了3次。这就说明在递归遍历二叉树的情况下，每一个节点调用的traversal方法片段都会被连续或者不连续访问3次。为什么？

这就要讲二叉树递归遍历方法的执行机制了。

2.2 递归执行机制

将2.1代码抽象化：

public static void traversal(Node root) {
    // 第一次访问区间
    if (root == null) {
        return ;
    }
    // 第一次访问区间
    traversal(root.left);
    // 第二次访问区间
    // 第二次访问区间
    traversal(root.right);
    // 第三次访问区间
    // 第三次访问区间
}
复制代码

以上代码是递归操作二叉树的骨架，利用该骨架，我们可以实现任何二叉树的操作。我们从Java函数调用机制来剖析该骨架的执行流程。

函数自上而下逐行执行：

• 第一次访问本方法：方法第一行执行 ——> traversal(root.left)开始递归调用

• 第二次访问本方法：traversal(root.left)结束递归调用 ——> traversal(root.right)开始递归调用

• 第三次访问本方法：traversal(root.right)结束递归调用 ——> 方法最后一行执行

每一次访问本方法，即使什么操作都没有，但是依旧会访问本方法的代码片段。

这就解释了为什么2.1递归遍历二叉树，每一个节点的value都会输出3次。因为在2.1的代码中，输出节点value的语句分别被放在了第一次访问区间，第二次访问区间和第三次访问区间。因此会随着3次访问本方法，三条输出语句被分别执行。

以二叉树某叶子节点为例，展示三次访问本方法代码片段：

2.3 递归遍历

在递归序的基础上，可以加工出三种顺序的递归遍历。先序，中序和后序遍历。

这三种递归遍历方法对于任何二叉树都适用。本质上就是利用递归执行机制，在三次访问本方法的过程中，选择不同的时机打印节点，从而实现了三种顺序的递归遍历。

2.3.1 前序遍历

定义：对于所有子树来说，都是先打印根节点，再打印左子树上所有节点，最后打印右子树上所有节点。

实现逻辑：在第一次访问本方法时打印节点，第二次和第三次不打印。

由2.1二叉树的递归序为 [ 1, 2, 4, 4, 4, 2, 5, 5, 5, 2, 1, 3, 6, 6, 6, 3, 7, 7, 7, 3, 1 ]

根据上述实现逻辑，加工递归序 [ 1(√), 2(√), 4(√), 4, 4, 2, 5(√), 5, 5, 2, 1, 3(√), 6(√), 6, 6, 3, 7(√), 7, 7, 3, 1 ]

可得前续遍历结果 [1, 2, 4, 5, 3, 6, 7]

代码：

public static void preOrderTraversal(Node root) {
    if (root == null) {
        return ;
    }
    System.out.println(root.value);
    preOrderTraversal(root.left);
    preOrderTraversal(root.right);
}
复制代码

2.3.2 中序遍历

定义：对于所有子树来说，先打印左子树上所有节点，再打印根节点，最后打印右子树上所有节点。

实现逻辑：在第二次访问本方法时打印节点，第一次和第三次不打印。

由2.1二叉树的递归序为 [ 1, 2, 4, 4, 4, 2, 5, 5, 5, 2, 1, 3, 6, 6, 6, 3, 7, 7, 7, 3, 1 ]

根据上述实现逻辑，加工递归序 [ 1, 2, 4, 4(√), 4, 2(√), 5, 5(√), 5, 2, 1(√), 3, 6, 6(√), 6, 3(√), 7, 7(√), 7, 3, 1 ]

可得中续遍历结果 [ 4, 2, 5, 1, 6, 3, 7 ]

代码：

public static void inOrderTraversal(Node root) {
    if (root == null) {
        return ;
    }
    inOrderTraversal(root.left);
    System.out.println(root.value);
    inOrderTraversal(root.right);
}
复制代码

2.3.3 后序遍历

定义：对于所有子树来说，先打印右子树上所有节点，再打印左子树上所有节点，最后打印根节点。

实现逻辑：在第三次访问本方法时打印节点，第一次和第二次不打印。

由2.1二叉树的递归序为 [ 1, 2, 4, 4, 4, 2, 5, 5, 5, 2, 1, 3, 6, 6, 6, 3, 7, 7, 7, 3, 1 ]

根据上述实现逻辑，加工递归序 [ 1, 2, 4, 4, 4(√), 2, 5, 5, 5(√), 2(√), 1, 3, 6, 6, 6(√), 3, 7, 7, 7(√), 3(√), 1(√) ]

可得后续遍历结果 [ 4, 5, 2, 6, 7, 3, 1 ]

代码：

public static void postOrderTraversal(Node root) {
    if (root == null) {
        return ;
    }
    postOrderTraversal(root.left);
    postOrderTraversal(root.right);
    System.out.println(root.value);
}
复制代码

2.4 非递归遍历

任何递归都可以改成非递归。因为递归又不是玄学，系统帮你压栈，你当然可以尝试着自己压栈来解决。

2.4.1 前序遍历

实现逻辑：

1. 准备一个栈。
2. 根节点最先压栈。
3. 迭代固定流程：
   1. 栈顶节点cur弹栈。
   2. 打印cur。
   3. cur的右孩子先压栈，左孩子再压栈。(如果存在的话)

代码：

public static void preOrderTraversal(Node root) {
    if (root == null) {
        return ;
    }
    Stack<Node> stack = new Stack<>();
    stack.push(root);
    while (!stack.empty()) {
        Node cur = stack.pop();
        System.out.println(cur.value);
        if (cur.right != null) {
            stack.push(cur.right);
        }
        if (cur.left != null) {
            stack.push(cur.left);
        }
    }
}
复制代码

2.4.2 中序遍历

实现逻辑：

1. 准备一个栈。
2. 迭代固定流程：
   1. 将根节点的左边界节点全部压栈。(如果存在的话)
   2. 栈顶节点弹栈，并打印。
   3. 将栈顶元素的右孩子作为新的根节点。(如果存在的话)

注意：左边界节点 = 根节点 + 根节点的所有左孩子

解释：为什么要这样操作可以实现非递归的中序遍历？因为，所有的树都是可以被左边界分解掉的。当然也是可以被右边界分解掉的，只是分解的角度不同而已。

我们把左边界按照先根再左的顺序压到栈里去，那么弹栈的顺序就先左再根。因此任何一个左边界打印的顺序都是先左再根，然后我们让一个节点弹出的时候，再让它右子树周而复始。

在这个流程中，打印的永远都是左边界，所以顺序永远的都是先左再根。关键是在进行先左再根的过程中，是让右孩子的左边界后去先左再根的。这说明，对于任何一个子树，都是如下过程：

代码：

public static void inOrderTraversal(Node root) {
    if (root == null) {
        return ;
    }
    Stack<Node> stack = new Stack<>();
    // 直到最右边的叶子节点弹栈后才结束,中途会出现栈空的情况
    while (!stack.isEmpty() || root != null) {
        if (root != null) {
            stack.push(root);
            root = root.left;
        } else {
            root = stack.pop();
            System.out.println(root.value);
            root = root.right;
        }
    }
}
复制代码

2.4.3 后序遍历

实现逻辑：

1. 准备两个栈。
2. 根节点最先压栈A。
3. 迭代固定流程：
   1. 栈顶节点cur弹栈A。
   2. cur入栈B。
   3. cur左孩子先压栈A，右孩子再压栈A。(如果存在的话)
4. 依次弹出栈B所有元素，同时打印。

代码：

public static void postOrderTraversal(Node root) {
    if (root == null) {
        return ;
    }
    Stack<Node> stackA = new Stack<>();
    Stack<Node> stackB = new Stack<>();
    stackA.push(root);
    while (!stackA.isEmpty()) {
        Node cur = stackA.pop();
        stackB.push(cur);
        if (cur.left != null) {
            stackA.push(cur.left);
        }
        if (cur.right != null) {
            stackA.push(cur.right);
        }
    }
    while (!stackB.isEmpty()) {
        System.out.println(stackB.pop().value);
    }
}
复制代码

2.5 深度优先遍历

前序遍历就是深度优先遍历。

public static void depthFirstSearch(Node root) {
    preOrderTraversal(root);
}
复制代码

2.6 宽度优先遍历

实现逻辑：

1. 准备一个队列。
2. 根节点先入队列。
3. 迭代固定流程：
   1. 队头节点cur出队列，并打印。
   2. cur左孩子入队列。(如果存在的话)
   3. cur右孩子入队列。(如果存在的话)

注意：

1. 在Java中，常用LinkedList模拟链式队列。
2. 队列的特性为FIFO（先进先出），队尾进元素，队头出元素。

代码：

public static void breadthFirstSearch(Node root) {
    if (root == null) {
        return ;
    }
    Queue<Node> queue = new LinkedList<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        Node cur = queue.poll();
        System.out.println(cur.value);
        if (cur.left != null) {
            queue.add(cur.left);
        }
        if (cur.right != null) {
            queue.add(cur.right);
        }
    }
}
复制代码

3. 二叉树的打印

在写二叉树调整的过程中，如果想看看当前二叉树变成了什么样子，就涉及到一个问题：如何直观打印一棵二叉树？

这里提供了一个福利函数，查看福利函数运行的结果时，将整个图顺时针转90°，就是当前的二叉树。

查看结果时注意：

• H1H：表示值为1的根节点。
• ^2^：表示该节点值为2，父节点在其左边偏上。
• v3v：表示该节点值为3，父节点在其左边偏下。

// 打印接口
public static void printBinaryTree(Node head) {
    System.out.println("Binary Tree:");
    printInOrder(head, 0, "H", 17);
    System.out.println();
}

public static void printInOrder(Node head, int height, String to, int len) {
    if (head == null) {
        return;
    }
    printInOrder(head.right, height + 1, "v", len);
    String val = to + head.value + to;
    int lenM = val.length();
    int lenL = (len - lenM) / 2;
    int lenR = len - lenM - lenL;
    val = getSpace(lenL) + val + getSpace(lenR);
    System.out.println(getSpace(height * len) + val);
    printInOrder(head.left, height + 1, "^", len);
}

public static String getSpace(int num) {
    String space = " ";
    StringBuffer buf = new StringBuffer("");
    for (int i = 0; i < num; i++) {
        buf.append(space);
    }
    return buf.toString();
}
复制代码

4. 序列化与反序列化

4.1 概念

二叉树的序列化指的是：将内存中的一棵二叉树序列化成字符串放入硬盘中存储。

二叉树的反序列化指的是：将硬盘中的字符串反序列化成一棵二叉树放入内存中存储。

每一种二叉树对应的都是唯一的字符串序列。

二叉树的序列化和反序列化的本质就是遍历，因此有多少种遍历方式就有多少种序列化方式，本文中使用前序遍历实现序列化。

4.2 序列化规则

整个二叉树字符序列由三部分构成：

• 每个节点的value
• _
• #

每个节点的value和value之间使用”_”分割。如果该节点为null，那么value用”#”代替。

图示：

4.3 代码

4.3.1 序列化

public static String serialize(Node root) {
    if (root == null) {
        return "#_";
    }
    StringBuilder charSequence = new StringBuilder();
    charSequence.append(root.value + "_");
    charSequence.append(serialize(root.left));
    charSequence.append(serialize(root.right));
    return charSequence.toString();
}
复制代码

4.3.1 反序列化

public static Node deserialize(String charSequence) {
    // 将字符序列拆开装进队列
    String[] values = charSequence.split("_");
    Queue<String> queue = new LinkedList<>();
    for (int i = 0; i < values.length; i ++) {
        queue.add(values[i]);
    }
    // 利用队列还原二叉树
    return process(queue);
}

public static Node process(Queue<String> queue) {
    String value = queue.poll();
    // 判断当前节点是否为null
    if ("#".equals(value)) {
        return null;
    }
    Node root = new Node(Integer.parseInt(value));
    root.left = process(queue);
    root.right = process(queue);
    return root;
}
复制代码

5. 特殊二叉树

5.1 搜索二叉树

5.1.1 定义

• 空二叉树是搜索二叉树。

• 非空二叉树的每一个根节点，它左子树上的节点的关键字都比它小，他右子树上的节点的关键字都比它大。

• 在一棵经典的搜索二叉树中，是没有重复节点的。

5.1.2 图示

5.1.3 判断搜索二叉树

思路：使用中序遍历遍历一棵搜索二叉树的结果一定是升序排列的。

注意：中序遍历可以用递归和非递归实现，但是在递归实现的过程中，无法在方法片段内保存前一个节点的关键字，从而必须定义类成员作为全局变量记录才可以。因此不推荐使用递归实现的中序遍历来判断搜索二叉树。

递归解法：

// 全局变量
private static Node pre = null;

public static boolean isBST(Node root) {
    if (root == null) {
        return true;
    }
    boolean isLeftBST = isBST(root.left);
    if (!isLeftBST) {
        return false;
    }
    // 升序判断
    if (pre != null && pre.value >= root.value) {
        return false;
    } else {
        pre = root;
    }
    return isBST(root.right);
}
复制代码

非递归解法：

public static boolean isBST(Node root) {
    if (root == null) {
        return true;
    }
    Stack<Node> stack = new Stack<>();
    // 记录当前节点的前一个节点
    Node pre = null;
    while (!stack.isEmpty() || root != null) {
        if (root != null) {
            stack.push(root);
            root = root.left;
        } else {
            Node cur = stack.pop();
            // 升序比较
            if (pre != null && pre.value >= cur.value) {
                return false;
            } else {
                pre = cur;
            }
            root = cur.right;
        }
    }
    return true;
}
复制代码

5.2 完全二叉树

5.2.1 定义

• 是满二叉树。

• 不是满二叉树，但是不满的层只可能是最后一层，即便是最后一层不满，也是从左到右依次变满的样子。

5.2.2 图示

5.2.3 判断完全二叉树

思路：

• 使用宽度优先遍历。
• 在遍历的过程中，如果遇到某个节点有右孩子没有左孩子，不是完全二叉树。
• 在遍历的过程中，如果遇到某个节点有左孩子没有右孩子或者都没有（左右子不全），那么之后遍历的节点必须都是叶子节点。

代码：

public static boolean isCBT(Node root) {
    if (root == null) {
        return true;
    }
    Queue<Node> queue = new LinkedList<>();
    queue.add(root);
    // 开关,遇到左右子不全的节点就触发并保持为true
    boolean flag = false;
    while (!queue.isEmpty()) {
        Node cur = queue.poll();
        // 判断当前节点是否有右孩子没有左孩子
        if (cur.left == null && cur.right != null) {
            return false;
        }
        // 判断当前节点是否无孩子或者有左孩子没有右孩子,第一次遍历到将触发flag
        if (cur.left == null || cur.right == null) {
            flag = true;
        }
        // 判断当flag置true后,遍历的节点是否都是叶子节点
        if (flag && !(cur.left == null && cur.right == null)) {
            return false;
        }
        if (cur.left != null) {
            queue.add(cur.left);
        }
        if (cur.right != null) {
            queue.add(cur.right);
        }
    }
    return true;
}
复制代码

5.3 满二叉树

5.3.1 定义

设最大深度为L，总节点数为N，满足 N = 2^L – 1的二叉树。

5.3.2 图示

5.3.3 判断满二叉树

思路：

1. 后序遍历求出树的深度。
2. 宽度优先遍历求出树的总节点数。
3. 根据公式 N = 2^L – 1 判断是否是满二叉树。

代码：

public static boolean isFBT(Node root) {
    if (root == null) {
        return true;
    }
    int depth = getDepth(root);
    int count = getCount(root);
    // 公式判断
    return count == (int) Math.pow(2, depth) - 1;
}

// 计算二叉树深度
public static int getDepth(Node root) {
    if (root == null) {
        return 0;
    }
    int leftD = getDepth(root.left);
    int rightD = getDepth(root.right);
    return Math.max(leftD, rightD) + 1;
}

// 计算二叉树总节点数
public static int getCount(Node root) {
    if (root == null) {
        return 0;
    }
    Queue<Node> queue = new LinkedList<>();
    queue.add(root);
    int count = 1;
    while (!queue.isEmpty()) {
        Node cur = queue.poll();
        if (cur.left != null) {
            queue.add(cur.left);
            count ++;
        }
        if (cur.right != null) {
            queue.add(cur.right);
            count ++;
        }
    }
    return count;
}
复制代码

5.4 平衡二叉树

5.4.1 定义

对于平衡二叉树中的任何一棵子树来说，它左子树的高度和它右子树的高度差都不超过1。

5.4.2 图示

5.4.3 判断平衡二叉树

思路：

1. 判断左子树是否为平衡二叉树。
2. 判断右子树是否为平衡二叉树。
3. 判断左子树和右子树的高度差的绝对值是否小于等于1。

注意：判断平衡二叉树的代码涉及到了二叉树的递归套路，详见6.3 。

代码：见 6.3 。

6. 二叉树的递归套路

6.1 内容

当在求解一个二叉树问题时，要以 “在我可以问我的左子树要信息，可以向我的右子树要信息的情况下，要什么样的信息，才能罗列出所有可能性” 作为切入点去思考问题。

步骤：

1. 确定判断条件。
2. 确定信息结构体。

该套路在解决二叉树的困难问题时非常之好用，可以解决一切树型DP问题！无非就是可能性的罗列有些难度。

包括以下讲的 “判断平衡二叉树”，”判断搜索二叉树” 等问题，都是树型DP问题。

树型DP问题也是面试关于二叉树题目中最难的题目。

注意：

该套路并不是可以解决所有二叉树的问题，但是可以解决大部分。该套路不能解决的二叉树问题往往非常麻烦，并且这类问题的解通常都是暴力解，无法被优化。（例如，找出整棵二叉树的中位数，我即使要到了左子树的中位数和右子树的中位数，对我整棵子树求中位数而言，没有任何意义）

只要该问题可以通过向左子树和右子树要信息，然后通过左右子树的信息调整当前整棵子树的信息，周而复始，进而解决整棵树的问题，都可以用该套路来解决。

6.2 代码结构

// 信息结构体
static class Info {
   ...
}

// 接口函数,返回值类型和方法名根据问题而定
public static xxx xxx(Node root) {
    ...
}

// 辅助过程函数
public static Info process(Node root) {
    // base case的返回值根据问题而定
    if (root == null) {
        return xxx;
    }
    // 收集左右子树的信息
    Info leftInfo = process(root.left);
    Info rightInfo = process(root.right);
    // 加工当前子树的信息
    ...
    // 返回当前子树的信息
    return new Info(xxx)
}
复制代码

6.3 案例分析

分析 5.4.3 “判断一棵树是否为平衡二叉树”，来描述二叉树的递归套路。

首先要清楚什么时平衡二叉树？

对于任何一个节点来说，它左子树的深度和它右子树的深度的深度差不超过1。

假设，当前节点x为根的子树，我要判断该子树是否为平衡二叉树，如何列可能性？这个可能性的组织，是基于可以向节点x的左子树要信息，可以向x的右子树要信心的情况下，如何列出可能性？

首先，确定判断条件。

本题中，如果该子树是平衡二叉树的话，必备三个条件：

1. 节点x的左子树是一棵平衡二叉树。
2. 节点x的右子树是一棵平衡二叉树。
3. 节点x的左子树和右子树的深度差不超过1。

根据排列组合，我们就能列出所有可能性，就能判断出各种情况。

其次，确定信息结构体。

因此，我们就能确定，需要向左子树和右子树要什么样子的信息。

本题中，我们确定了需要向左子树和右子树要 [ 是否平衡，深度 ] 两个信息，左树和右树的要求是一样的。

代码：

// 信息结构体
static class Info {
    boolean isBBT;
    int depth;
    R(boolean isBBT, int depth) {
        this.isBBT = isBBT;
        this.depth = depth;
    }
}

public static boolean isBBT(Node root) {
    return process(root).isBBT;
}

public static Info process(Node root) {
    if (root == null) {
        return new Info(true, 0);
    }
    // 获取左右子树的信息
    Info leftInfo = process(root.left);
    Info rightInfo = process(root.right);
    // 当前子树的高度
    int depth = Math.max(leftInfo.depth, rightInfo.depth) + 1;
    boolean isBBT = false;
    // 判断当前节点是否左右子树都平衡且左右子树高度差不超过1
    if (leftInfo.isBBT && rightInfo.isBBT && Math.abs(leftInfo.depth - rightInfo.depth) <= 1) {
        isBBT = true;
    }
    // 返当前子树的信息
    return new Info(isBBT, depth);
}
复制代码

6. 面试题

6.1 二叉树最大宽度

题目：求一棵二叉树的最大宽度。

思路：

在二叉树宽度优先遍历的基础上，增加记录每一层的宽度的机制，记录的同时逐层比较出一个最大宽度。

记录每一层宽度的机制主要体现在：

• 使用两个变量，分别记录当前层和当前层节点数。
• 使用HashMap记录每一个节点的所属层数。

当当前层数和当前遍历节点的所属层数不一致的时候，表示当前层遍历结束，已经遍历到了当前层下一层的最左节点，这时就可以统计当前层记录的总节点数，其他层同理。

代码：

public static int getMaxBreadth(Node root) {
    if (root == null) {
        return -1;
    }
    // 当前层
    int curLayer = 1;
    // 当前层节点数
    int curLayerNodesNum = 0;
    // 最宽层节点点数
    int broadestLayerNodesNum = Integer.MIN_VALUE;
    // 辅助表,用来记录每一个节点的层数
    HashMap<Node, Integer> map = new HashMap<>();
    
    Queue<Node> queue = new LinkedList<>();
    queue.add(root);
    // 根节点层数先记录进表中
    map.put(root, 1);
    
    // 队列空时结束
    while (!queue.isEmpty()) {
        Node cur = queue.poll();
        // 获取当前节点层
        int curNodeLayer = map.get(cur);
        // 判断该节点是否在当前层
        if (curNodeLayer == curLayer) {
            curLayerNodesNum ++;
        } else {
            // 和当前最宽层节点数进行比较出一个更大的
            broadestLayerNodesNum = Math.max(broadestLayerNodesNum, curLayerNodesNum);
            // 当前层进入下一层
            curLayer ++;
            // 初始化下一层节点数
            curLayerNodesNum = 1;
        }
        if (cur.left != null) {
            queue.add(cur.left);
            // 当前节点左子节点的所属层数记录进表
            map.put(cur.left, curNodeLayer + 1);
        }
        if (cur.right != null) {
            queue.add(cur.right);
            // 当前节点右子节点的所属层数记录进表
            map.put(cur.right, curNodeLayer + 1);
        }
    }
 	// 循环结束时,最后一层的节点数还没有和最宽层节点数作比较,需要手动比较
   	return Math.max(broadestLayerNodesNum, curLayerNodesNum);
}
复制代码

6.2 判断满二叉树

题目：判断一棵树是否是满二叉树。

思路：

使用二叉树的递归套路。

判断条件为：该题没有判断条件，只需要收集子树的深度和总结点数。最后使用满二叉树公式统一判断。

信息结构体为：[ 当前树的深度，当前树的总节点数 ]

代码：

static class Info {
    // 树的深度
    int depth;
    // 树的节点总数
    int count;
    public Info(int depth, int count) {
        this.depth = depth;
        this.count = count;
    }
}

public static boolean isFBT(Node root) {
    Info info = process(root);
    int depth = info.depth;
    int count = info.count;
    // return count == (int) Math.pow(2, depth) - 1;
    return count == (1 << depth) - 1;
}

public static Info process(Node root) {
    if (root == null) {
        return new Info(0, 0);
    }
    Info leftInfo = process(root.left);
    Info rightInfo = process(root.right);
    // 当前树的深度
    int depth = Math.max(leftInfo.depth, rightInfo.depth) + 1;
    // 当前树的总节点数
    int count = leftInfo.count + rightInfo.count + 1;
    return new Info(depth, count);
}
复制代码

6.3 判断搜索二叉树

题目：判断一棵树是否是搜索二叉树。

思路：

使用二叉树的递归套路。

这道题目和判断平衡二叉树稍有不同，判断平衡二叉树的左右子树要求是一样的，所以信息结构体很好确定。在本题中，左右子树的要求不一样，所以信息结构体需要取左右子树分别要求的信息的全集。

判断条件为：

1. 节点x的左子树是一棵搜索二叉树。
2. 节点x的右子树是一棵搜索二叉树。
3. 节点x的左子树的最大关键字 < x 。
4. 节点x的右子树的最小关键字 > x 。

信息结构体为：[ 是否是搜索二叉树，当前树的最大关键字，当前树的最小关键字 ]

代码：

// 信息结构体
static class Info {
    // 当前树是否是搜索二叉树
    boolean isSBT;
    // 当前树中最大关键字
    int maxValue;
    // 当前树中最小关键字
    int minValue;
    public R(boolean isSBT, int maxValue, int minValue) {
        this.isBST = isSBT;
        this.maxValue = maxValue;
        this.minValue = minValue;
    }
}

public static boolean isSBT(Node root) {
    return process(root).isSBT;
}

public static Info process(Node root) {
    if (root == null) {
        return null;
    }
    Info leftInfo = process(root.left);
    Info rightInfo = process(root.right);
    boolean isSBT = true;
    // 初始化值为自身关键字
    int maxValue = root.value;
    int minValue = root.value;
    // 从左右子树中找出最大关键字和最小关键字给自身赋值
    if (leftInfo != null) {
        maxValue = Math.max(leftInfo.maxValue, maxValue);
        minValue = Math.min(leftInfo.minValue, minValue);
    }
    if (rightInfo != null) {
        maxValue = Math.max(rightInfo.maxValue, maxValue);
        minValue = Math.min(rightInfo.minValue, minValue);
    }
    // 当左子树存在,左子树不是BST或者当前节点的关键字小于左子树的最大关键字
    if (leftInfo != null && (!leftInfo.isSBT || leftInfo.maxValue >= root.value)) {
        isSBT = false;
    }
    // 当右子树存在,右子树不是BST或者当前节点的关键字大于右子树的最小关键字
    if (rightInfo != null && (!rightInfo.isSBT || rightInfo.minValue <= root.value)) {
        isSBT = false;
    }
    return new Info(isSBT, maxValue, minValue);
}
复制代码

注意：

在这道题的代码中，按照二叉树的递归套路，process方法中的base case原本应该返回new R(true, xxx, xxx)，但是minValue和maxValue的处理很棘手，赋成什么值都感觉不合适。在这个时候，就可以返回null，但是注意在调用时，需要对是否为null加以条件判断。

6.4 找最低公共祖先

题目：给定一棵二叉树中的两个节点node1和node2，找到它们的最低公共祖先节点。

注意：最低公共祖先节点指的是node1和node2往上第一个汇聚的节点。

6.4.1 一般解法

思路：构建一个HashMap作为整棵树的父节点表，存着树中每一个节点和其父节点的对应关系（根节点的父节点是自己）。然后再构建一个HashSet，先将node1到根节点这条链中所有的节点全部存入，再将node2到根节点这条链中的节点依次存入。利用HashSet的元素不重复性，当node2到根节点这条链中的某个节点在存入时，导致HashSet元素冲突，那么该节点就是最低公共祖先节点。

代码：

public static Node lowestCommonAncestor(Node root, Node node1, Node node2) {
    if (root == null) {
        return null;
    }
    HashMap<Node, Node> map = new HashMap<>();
    // 根节点入表,其父节点设置为自身
    map.put(root, root);
    // 其余节点入表
    process(root, map);
    HashSet<Node> set = new HashSet<>();
    // 根先入辅助容器
    set.add(root);
    // 将node1到根节点链条上所有节点入容器
    Node cur = node1;
    while (cur != map.get(cur)) {
        set.add(cur);
        cur = map.get(cur);
    }
    // 将node2到根节点链条上所有节点入容器
    cur = node2;
    while (true) {
        // 必然会造成节点冲突并返回
        if (set.contains(cur)) {
            return cur;
        }
        set.add(cur);
        cur = map.get(cur);
    }
}

public static void process(Node root, HashMap<Node, Node> map) {
    if (root == null) {
        return ;
    }
    process(root.left, map);
    process(root.right, map);
    // 左右子节点入表
    if (root.left != null) {
        map.put(root.left, root);
    }
    if (root.right != null) {
        map.put(root.right, root);
    }
}
复制代码

6.4.2 优化解法

思路：

根据题目要求，无非就只会出现三种情况：

1. node1是node2的最低公共祖先节点。
2. node2是node1的最低公共祖先节点。
3. node1和node2不互为最低公共祖先节点。

所有结构关系就可以分为两类：

1. 两个节点的最低公共祖先节点是其中一个（情况1，2）。
2. 两个节点不互为最低公共祖先节点（情况3）。

代码：

public static Node lowestCommonAncestor(Node root, Node node1, Node node2) {
    if (root == null || root == node1 || root == node2) {
        return root;
    }
    Node left = lowestCommonAncestor(root.left, node1, node2);
    Node right = lowestCommonAncestor(root.right, node1, node2);
    if (left != null && right != null) {
        return root;
    }
    return left != null ? left : right;
}
复制代码

分析：

如果一棵子树上，既没有node1，也没有node2，那么返回的一定是null。

如果一棵子树上有node1和node2，其中一个节点作为该子树的根，那么返回的就是作为根的节点。

如果一棵子树上有node1和node2，两个节点都不是该子树的根，那么返回的就是两个节点最先汇聚的节点。

6.5 找后继节点

题目：现在有一种新的二叉树节点类型如下:

public class Node {
	int value;
    Node left;
    Node right;
    Node parent;
}
复制代码

该结构和经典二叉树节点结构的不同在于多了一个指向父节点的parent指针。

假设有一棵该Node类型的节点组成的二叉树，树中每个节点的parent指针都正确指向自己的父节点，头节点的parent指向null。只给一个在二叉树中的某个节点node，找到node的后继节点。

要求：时间复杂度小于O(N)。

注意：

• 后继节点：在二叉树的中序遍历的序列中，node的下一个节点叫做node的后继节点。

• 前驱节点：在二叉树的中序遍历的序列中，node的前一个节点叫做node的前驱节点。

分析：

时间复杂度小于O(N)，意味着不能使用查看中序遍历序列的方法找到后继节点。

我们定义，单个指向的距离为1。

如图所示，D节点的后继节点是B节点，两个节点在树上的距离就是1，D节点可以直接通过parent找到B节点。E节点的后继节点是A节点，两个节点在树上的距离是2，E节点可以通过parent寻址两次找到A节点。

我们设想，如果任何节点都有指向父节点的指针的话，假设Y节点是X节点的后继节点，且两节点的距离为K，我们能否将时间复杂度降到O(K)，而不是去遍历所有节点得出中序遍历序列。

因此，理论上来说，一个节点找后继节点这个过程，只需要让parent进行指定距离次数的寻址就可以找到后继节点，那么是否存在优化的可能性？那么我们就需要考虑一个问题，一个节点的后继节点如何在结构上找到？

从结构上进行分析，只有三种可能：

• 如果X节点有右子树，那么X节点的后继节点为其右子树的最左节点。

• 如果X节点没有右子树，那么从X节点开始向上遍历，如果寻址到的某个祖先节点是自己父节点的左孩子，那么该祖先节点的父节点就是X节点的后继节点（对于后继节点来说，X节点是其左子树中的最右节点）。

• 如果X节点是整棵树的最右节点，那么该节点没有后继节点，为null。

代码：

public static Node findSuccessorNode(Node root, Node target) {
    if (root == null) {
        return null;
    }
    Node cur = target.right;
    // 目标节点存在右子树
    if (cur != null) {
        while (cur.left != null) {
            cur = cur.left;
        }
        return cur;
    }
    // 目标节点没有右子树
    else {
        cur = target;
        while (cur.parent != null) {
            if (cur == cur.parent.left) {
                return cur.parent;
            }
            cur = cur.parent;
        }
        // 当该节点是整棵树最右节点时,后缀节点是null
        return null;
    }
}
复制代码

6.6 折纸问题

题目：

把一段纸条竖着放在桌子上，然后从纸条的下边向上方对折1次，压出折痕后展开，此时这条折痕是凹下去的。

如果从纸条的下边向上方连续对折2次，压出折痕后展开，此时有3条折痕，从上到下依次是凹折痕，凹折痕，突折痕。

给定一个输入参数 N，代表着纸条从下往上连续对折 N 次，请从上到下打印所有折痕的方向，凹折痕方向为下，凸折痕方向为上。

例如：

N = 1时，打印 down

N = 2时，打印 down down up

分析：

先看三次对折的折痕状况：

• 第一次对折后，出现了一条凹折痕。

• 第二次对折后，1折痕的上下两侧，出现了新条纹，上面的是凹折痕，下面的是凸折痕。

• 第三次对折后，每一条2折痕的上下两侧，出现了新条纹，上面的是凹折痕，下面的是凸折痕。

可以发现一个规律：新凹折痕永远在前一次折痕的相邻上方，新凸折痕永远在前一次折痕的相邻下方。

因此，可以将折痕的结果通过递归模拟成一棵二叉树，该二叉树的根节点为凹折痕，每一棵左子树的根节点都为凹折痕，每一棵右子树的根节点都是凸折痕。

从上到下打印折痕情况就是该二叉树的中序遍历。

代码：

public static void paperFolding(int N) {
    // 第一次折痕为down
    process(N, 1, true);
}

/**
     * @param N 对折的次数 —— 二叉树的深度
     * @param depth 节点的深度
     * @param direction 折痕的方向,true为down,false为up
     */
public static void process(int N, int depth, boolean direction) {
    if (depth > N) {
        return ;
    }
    // 左孩子都是down
    process(N, depth + 1, true);
    System.out.print(direction ? "down " : "up ");
    // 右孩子都是up
    process(N, depth + 1, false);
}
复制代码