【数据结构】树

二叉树的遍历

二叉树的前序、中序、后序遍历本质上就是将打印语句放到 “第一次来到该节点、第二次回到该节点、第三次回到该节点” 的位置。

public static void traversal(Node head) {
    if (head == null) {
        return;
    }

    // --------------------------------
    // 第一次来到该节点, 对应前序
    // 访问其左右子树前, 就会来到这里
    // --------------------------------

    // 递归遍历左子树
    traversal(head.left);

    // --------------------------------
    // 第二次回到该节点, 对应中序
    // 访问完其整个左子树后, 才会来到这里
    // --------------------------------

    // 递归遍历右子树
    traversal(head.right);

    // --------------------------------
    // 第三次回到该节点, 对应后序
    // 访问完其整个右子树后, 才会来到这里
    // --------------------------------
}

前序遍历

前序遍历：头 -> 左 -> 右

递归方式

public static void preOrderRecur(Node head) {
    if (head == null) {
        return;
    }
    System.out.print(head.value + " ");
    preOrderRecur(head.left);
    preOrderRecur(head.right);
}

非递归方式：借助一个栈结构

后序遍历的非递归方式需要借助两个栈，步骤和前序遍历相似，只不过将一个栈中的元素压入到另一个栈后再统一出栈打印

非递归的前序遍历，需要使用一个栈结构。

先将根节点入栈，然后不断循环，按照 “弹栈打印 -> 右孩子入栈 -> 左孩子入栈” 的顺序遍历，即可实现前序遍历。

因为每次都将右孩子先入栈，同时弹出左孩子时就立刻再次压入其右孩子和左孩子，所以某个节点的右子树会堆积在栈底，一直到其左子树都弹栈后才会再遍历，从而达到了先序遍历的效果。

//    1. 首先, 树的根结点先入栈,
//       while (栈不空) {
//    2.    弹出栈顶节点并打印
//    3.    先将右孩子入栈, 再将左孩子入栈 (注意先后顺序要先右再左, 这样弹栈时就会先弹左再弹右)
//       }
// 因为每次都将右孩子先入栈，同时弹出左孩子时就立刻再次压入其右孩子和左孩子，所以某个节点的右子树
// 会堆积在栈底，一直到其左子树都弹栈后才会再遍历，从而达到了先序遍历的效果
// 总结: 先弹顶 -> 压左 -> 压右 -> 弹栈 -> 压左 -> 压右

// 前序遍历的效果: 先把根结点的左子树上的所有节点遍历后才会遍历右子树
//                并且每个子树都遵循该效果
public static void preOrderUnRecur(Node head) {
    if (head != null) {
        Stack<Node> stack = new Stack<>();
        stack.push(head);
        Node cur = null;
        while (!stack.isEmpty()) {
            cur = stack.pop();
            System.out.print(cur.value + " ");

            if (cur.right != null) {
                stack.push(cur.right);
            }
            if (cur.left != null) {
                stack.push(cur.left);
            }
        }
    }
}

中序遍历

中序遍历：左 -> 头 -> 右

递归方式

public static void inOrderRecur(Node head) {
    if (head == null) {
        return;
    }
    inOrderRecur(head.left);
    System.out.print(head.value + " ");
    inOrderRecur(head.right);
}

非递归方式：借助一个栈结构

思路：把整棵树按照左边界进行分解，同时右孩子节点也按照左边界分解，将右子树的节点也依次左孩子节点入栈。即每打印一个节点后就把右子树的节点也依次左孩子节点入栈。

// 直将当前节点的所有左孩子都入栈，直到当前节点没有了左孩子，
//则将当前节点弹栈并打印，同时将当前节点的右孩子节点的所有左孩子节点都入栈

// 遍历到某个叶子节点时, 其左右孩子节点都是 null
//  先 if 发现是 null , 进入 else 弹出并打印该叶子节点，然后再获取右孩子, 又是 null
//  再进一次  while  发现还是走 else，弹出了其父节点, 然后打印
// 所以连起来看就是 左 -> 头 -> 右

// 因为左边界是按照先入头再入左的顺序, 因此弹栈时就是先左再头
// 每次都是先左再头, 然后再让其右子树进行先左再头, 周而复始

// 思想: 把整棵树按照左边界进行分解, 同时右孩子节点也按照左边界分解,
// 将右子树的节点也依次左孩子节点入栈
// 左 -> 头 -> 右(左 -> 头 -> 右(左 -> 头 -> 右(...)))
public static void inOrderUnRecur(Node head) {
    if (head != null) {
        Stack<Node> stack = new Stack<>();
        // 注意: 一开始不需要入根结点

        // 注意循环终止条件需要加上 head != null
        while (!stack.isEmpty() || head != null) {
            // 每次循环到这里, 栈顶保存着当前 head 的父节点
            if (head != null) {
                // 一直将当前节点入栈, 每次压栈后栈顶保存的都是父节点, 也就是 头
                stack.push(head);
                // 注意是先压栈, 再指向左孩子, 这样在进入 else 时,
                // 栈顶节点保存的就是当前父节点, 从而在弹出栈顶节点后, 就可以获取到其右孩子
                head = head.left;
            } else {
                // 弹出当前栈顶节点, 引入入栈时是先入的左, 再入的头
                // 所以这里弹出时先弹出的是左, 然后才是头,
                // 接着将右子树进行分解, 再进行一次左边界的递归入栈
                head = stack.pop();
                System.out.print(head.value + " ");
                // 一个节点弹出时, 再让其右子树进行一次左边界的递归入栈:
                // 令 head 指向当前节点的右孩子, 从而在接下来进入 if 判断后,
                // 将当前节点的右孩子(已经变为了head)的所有左孩子节点入 栈
                head = head.right;
            }
        }
    }
}

后序遍历

后序遍历：左 -> 右 -> 头

递归方式

public static void posOrderRecur(Node head) {
    if (head == null) {
        return;
    }
    posOrderRecur(head.left);
    posOrderRecur(head.right);
    System.out.print(head.value + " ");
}

非递归方式：借助两个栈结构

后序遍历的非递归方式需要借助两个栈，步骤和前序遍历相似，只不过将一个栈中的元素压入到另一个栈后再统一出栈打印。

非递归的后序遍历，需要使用两个栈结构，另一个栈用于存储第一个栈弹出的节点

// 首先, 按照 先弹顶并压入栈2 -> 压左 -> 压右 的顺序执行
// 然后依次弹出栈2中的节点并打印, 这样第二个栈再弹出时打印的顺序就是 左右头

//   (头在最后打印的原因时, 入第一个栈时, 在压当前节点的左右孩子节点前先将当前节点弹出并压到了栈2
//   然后弹其右孩子节点时就会存放到了当前节点的上面, 最后才是压入其左孩子节点
//   所以从栈2弹出时的顺序就是  左 -> 右 -> 头)
//
//   流程:
//    1. 首先, 树的根结点先入栈,
//       while (栈1不空) {
//    2.    弹出栈1的顶节点并压入栈2(不打印)
//    3.    先将左孩子入栈, 再将右孩子入栈 (注意先后顺序和前序相反)
//       }
//    4. 依次弹出栈2的每个节点并打印
public static void posOrderUnRecur1(Node head) {
    if (head != null) {
        Stack<Node> stack1 = new Stack<>();
        Stack<Node> stack2 = new Stack<>();
        Node cur = head;
        stack1.push(head);

        while (!stack1.isEmpty()) {
            cur = stack1.pop();
            stack2.push(cur);
            if (cur.left != null) {
                stack1.push(cur.left);
            }
            if (cur.right != null) {
                stack1.push(cur.right);
            }
        }

        // 依次弹出栈2的节点
        while (!stack2.isEmpty()) {
            System.out.print(stack2.pop().value + " ");
        }
    }
}

前序、中序、后序遍历在数组中的体现

• 知道前序遍历序列和中序遍历序列，可以唯一确定一颗二叉树
• 知道后序遍历序列和中序遍历序列，可以唯一确定一颗二叉树

但是只知道后序和前序无法唯一确定一棵二叉树，因为需要中序序列中定位到根节点的位置才可以进行左右侧划分，否则不知道前序或后序序列中左右子树的划分边界

根节点位置：

• 前序遍历：在数组的第一个位置
• 中序遍历：在数组的中间某个位置（第一个位置为整棵树最左侧的节点）
• 后序遍历：在数组的最后一个位置

左右子树的分布特点：

• 前序遍历：根 -> 左 -> 右
• 中序遍历：左 -> 根 -> 右
• 后序遍历：左 -> 右 -> 根

具体分布可见下图：

相关题目可见：重建二叉树与二叉搜索树的后续遍历序列。

层次遍历

层次遍历常用于和树的宽度相关或需要知道当前节点所在层信息的题目，例如求树的最大宽度，或者判断完全二叉树。

层次遍历常常与队列一起组合出现，因为使用队列先进先出的特点才能保证做到层次遍历，如果是栈结构的先进后出，就无法做到层次遍历。

层次遍历的一个技巧，可以在进入每层后，首先获取队列中节点的个数，其就代表了当前层的节点数目，那么就可以在开启一个内层 while 循环，一次性遍历当前层的所有节点。

代码：

public void levelOrder(Node head) {
    if (head == null)
        return;

    Queue<Node> queue = new LinkedList<>();
    queue.add(head);

    while (!queue.isEmpty()) {
        int size = queue.size();
        // 依次遍历当前层内所有节点
        while (size-- > 0) {
            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);
        }
    }
}

按照之字形进行层次遍历

之字形遍历即要求奇数层从左往右打印，偶数层从右往左打印。要实现该功能，有三种思路：

• 仍然采用传统的层次遍历，只不过在最后对偶数层集合进行逆序；或在偶数层添加元素时从后往前加入到结果集合 LinkedList<>#addLast() 中
• 使用两个栈结构。一个栈存储奇数层的节点，一个栈存储偶数层的节点
  • 遍历奇数层时，向偶数栈中压入当前层的孩子；先左后右
  • 遍历偶数层时，向奇数栈中压入当前层的孩子；先右后左
• 使用一个双端队列结构。每次不止遍历两层，而是先遍历奇数层，再遍历偶数层
  • 奇数层是从头出，从尾入；先左后右
  • 偶数层是从尾出，从头入；先右后左
  • 注意：出和入的方向肯定是相反的，不然就会导致刚入的，就要出了

代码：

public List<List<Integer>> levelOrder(TreeNode root) {
    if (root == null) {
        return new ArrayList<>();
    }

    // 1. 两个栈，一个栈存储奇数层的，一个栈存储偶数层的
    // 遍历奇数层时，向偶数栈中压入当前层的孩子；先左后右
    // 遍历偶数层时，向奇数栈中压入当前层的孩子；先右后左

    // 2. 双端队列，每次不止遍历两层，而是先遍历奇数层，再遍历偶数层
    // 奇数层是从头出，从尾入；先左后右
    // 偶数层是从尾出，从头入；先右后左
    // 注意：出和入的方向肯定是相反的，不然就会导致刚入的，就要出了

    return levelOrderDeque(root);
}

// 1. 双栈
public List<List<Integer>> levelOrderTwoStack(TreeNode root) {
    List<List<Integer>> res = new ArrayList<>();
    Stack<TreeNode> stackOdd = new Stack<>();
    Stack<TreeNode> stackEven = new Stack<>();
    stackOdd.push(root);

    // 两个栈分别存储奇数层和偶数层的元素
    // 如果同时为空，说明遍历完了
    while (!stackOdd.isEmpty() || !stackEven.isEmpty()) {
        List<Integer> list = new ArrayList<>();
        // 刚来到新的一层时只会有一个栈不为空
        if (!stackOdd.isEmpty()) {
            // 如果奇数层栈不为空，则当前是奇数层
            // 奇数层先入左孩子，再入右孩子
            while (!stackOdd.isEmpty()) {
                root = stackOdd.pop();
                list.add(root.val);
                if (root.left != null) {
                    stackEven.push(root.left);
                }
                if (root.right != null) {
                    stackEven.push(root.right);
                }
            }
        } else {
            // 否则当前就是偶数层
            // 偶数层先入右孩子，再入左孩子
            while (!stackEven.isEmpty()) {
                root = stackEven.pop();
                list.add(root.val);
                if (root.right != null) {
                    stackOdd.push(root.right);
                }
                if (root.left != null) {
                    stackOdd.push(root.left);
                }
            }
        }
        res.add(list);
    }
    return res;  
}

// 2. 双端队列
public List<List<Integer>> levelOrderDeque(TreeNode root) {
    Deque<TreeNode> queue = new LinkedList<>();
    List<List<Integer>> res = new ArrayList<>();
    queue.addFirst(root);

    while (!queue.isEmpty()) {
        int size = queue.size();
        List<Integer> list = new ArrayList<>();    
        // 先遍历奇数层，然后紧接着判断是否还有偶数层，如果有就接着遍历
        while (size-- > 0) {
            // 奇：从头出，从尾入；先左后右
            root = queue.removeFirst();
            list.add(root.val);
            if (root.left != null) {
                queue.addLast(root.left);
            }
            if (root.right != null) {
                queue.addLast(root.right);
            }
        }
        res.add(list);

        // 处理过奇数层，立刻处理偶数层
        if (!queue.isEmpty()) {
            size = queue.size();
            list = new ArrayList<>();    
            while (size-- > 0) {
                // 偶：从尾出，从头入；先右后左
                root = queue.removeLast();
                list.add(root.val);
                // 每次都是先右后左的顺序入队头，这样就会导致奇数层可以做到从左往右遍历
                if (root.right != null) {
                    queue.addFirst(root.right);
                }
                if (root.left != null) {
                    queue.addFirst(root.left);
                }
            }
            res.add(list);
        }
    }
    return res;
}

Morris 遍历

实现流程

假设来到当前节点 cur，开始时 cur 在头节点位置

• 如果 cur 没有左孩子，则 cur 向右移动 cur = cur.right（这里会因为事先建立的线索而再次回到上层节点）
• 如果 cur 有左孩子，找到 cur 的左子树上的最右侧节点 mostRight：
  • 如果 mostRight 的右指针指向空（说明是第一次到该节点，还没建立线索），让其指向 cur（mostRight.right = cur），此时建立了当前节点左子树最右节点与当前节点间的线索。然后 cur 向左移动 cur = cur.left，开始向左子树遍历
  • 如果 mostRight 的右指针指向 cur（说明是第二次到该节点，之前就建立过线索了），让其指向 null（取消线索），断开了之前建立的线索，恢复了最右节点的原始结构。然后 cur 向右移动 cur = cur.right。开始向右子树遍历
• cur 为 null 时遍历停止

上述流程可分为三个阶段：

• 线索化：第一次来到某节点 A，寻找其 mostRight 并赋值 mostRight.right = A。借助于该线索才能在访问过节点 A 的左子树的全部节点后再次回到节点 A。如果不线索化，访问了底层节点后就不能再回到节点 A 了。接着 cur = cur.left，即开始向左子树遍历
• 遍历左子树：A 完成线索化后，开始向左子树遍历。当遍历到刚才的 mostRight 时，将通过之前创建的线索进行回溯，重新回到 A：cur = cur.right
• 取消线索化：第二次回到节点 A 时，寻找其 mostRight 并赋值 mostRight.right = null。此时是第二次回到节点 A，其左子树上的全部节点都已经遍历完毕了，接着该向其右子树进行遍历了。因此 cur = cur.right

上述三个阶段的图示：

建立线索——消除线索的过程：

• 开始时所有子树的最右节点的 right 都是 null，此时还没建立起线索
• 接着第一次来到某个节点 A 时，若其左子树的最右节点存在，则会建立该最右节点与当前节点的线索，具体方法是：mostRight.right = A。然后当前节点继续向左移动：cur = A.left。注意：这里建立的线索将会在后续遍历到 mostRight 节点时，执行 cur = mostRight.right 语句来再次回到节点 A
• 当 cur 在向左子树不断遍历的过程中来到刚才建立线索的最右节点 mostRight 时，会执行 cur = mostRight.right 语句重新回到其线索指向的祖先节点 A，从而做到了第二次回到节点 A
• 第二次回到节点 A 后，继续寻找其左子树上的最右节点 mostRight，然后取消线索化：mostRight.right = null，从而恢复其原始结构

线索化的目的：在访问了底层节点后，依旧能借助该线索再次回到上层的节点，从而继续向右侧迭代遍历。如果不线索化，访问了底层节点后就不能再回到上层节点了。

左子树上的线索化结果图示：

算法复杂度

没有左孩子的节点只会被遍历一次（因为找不到 mostRight，没有能回溯的线索）；有左孩子的节点会被遍历两次（第二次是通过线索回溯到的）：

• 有左孩子，则该节点会被访问两次
  • 第一次访问时，其左子树上的最右节点的右孩子为 null
  • 第二次访问时，其左子树上的最右节点的右孩子为该节点
• 没左孩子，则该节点只会被访问一次

复杂度：

• 时间复杂度：不同的节点寻找 mostRight 的路径是完全不重合的，因此时间复杂度并没有增加太多，最多是 O(2N)，也还是 O(N)。
• 空间复杂度：O(1)。全局只需要存储 cur 和 mostRight，也没有利用系统栈，不耗费额外空间。

总结

传统递归的方式进行遍历时，是通过系统压栈的方式告诉我们当前节点是第几次被访问，每个节点会被访问三次；但 Morris 遍历并不是，其只能模拟：在左子树上转一圈后回到自身，不能在右子树上转一圈后回到自身（即无法第三次回到自身）。它是利用线索化的机制回到当前节点。

Morris 遍历的特点：可以选择是否要第二次回到当前节点（实现方式为通过当前节点左子树的底层节点的线索化，将right指针指向当前节点来实现）

借助于 Morris 遍历，可以实现出时间复杂度为 O(N)，空间复杂度为 O(1) 的前序、中序以及后序遍历。

Morris 遍历代码：

public static void morrisTraversal(TreeNode root) {
    if (root == null) {
        return;
    }
    TreeNode cur = root;
    TreeNode mostRight;
    while (cur != null) {
        // Morris 顺序打印位置:
        System.out.print(cur.value + " ");
        // 有两种情况会来到某个节点:
        // 1. 第一次来到当前节点, 通过 cur = cur.left 或 cur = cur.right 方式
        // 2. 第二次回到当前节点, 通过线索节点的 cur = cur.right 进行回溯
        // 只要某个节点有左孩子, 就能线索化, 从而就能第二次回到当前位置

        // 先尝试寻找左子树上的最右节点
        mostRight = cur.left;

        // 如果当前节点存在左子树, 则开始寻找其 mostRight
        if (mostRight != null) {
            // 一直寻找 cur 左子树上的最右节点, 可能有两种情况:
            // 1. mostRight.right == null, 则代表还未建立线索
            // 2. mostRight.right == cur, 则代表已经建立了线索
            while (mostRight.right != null && mostRight.right != cur) {
                mostRight = mostRight.right;
            }
            // 1. mostRight.right == null, 则代表还未建立线索
            // 此时是第一次到达 mostRight 与节点 A, 需要建立二者的线索
            if (mostRight.right == null) {
                mostRight.right = cur;
                // ========================================================
                // 此时是节点 A 第一次找到 mostRight, 同时也是第一次访问节点 A
                // 因为只有在访问到节点 A 时, 才会去寻找其 mostRight
                // ========================================================
                // 在这里打印, 就能符合前序遍历中先打印头的要求
                // System.out.print(cur.value + " ");

                // 线索化后, cur 开始遍历左子树
                cur = cur.left;
                // 进入下一次循环, 开始遍历左子树
                // 这里的 continue 非常重要，能够令当前节点 A 不经过下面的 cur = cur.right; 直接进入到其左子树上进行遍历
                // 这样就有效地做到了第一次到当前节点时不处理，第二次到当前节点时（在接下来的 else 里）处理，从而很好地实现了中序遍历
                continue;
            } else {
                // 2. mostRight.right == cur, 则代表已经建立了线索
                // ========================================================
                // 此时为第二次到达 mostRight, 也是第二次到达之前访问过的节点 A
                // (通过 mostRight 回溯到了 A), 需要取消二者的线索
                // 此时是节点 A 第二次找到 mostRight, 同时也是第二次访问节点 A,
                // 因为只有在访问到节点 A 时, 才会去寻找其 mostRight
                // ========================================================
                mostRight.right = null;
                // 第二次到达节点 A 后, 就会走出这里, 到下面继续执行 cur = cur.right, 从而开始遍历右子树
                // 通过在下面增加 else 分支就可以控制第二次到达节点 A 时不打印，从而实现中序遍历
            }
        }
        // 两种情况:
        // 1. 到达某个节点的 mostRight, 通过其 right 线索回溯到其祖先节点
        // 2. 第二次回到祖先节点, 代表左子树遍历完毕了, 开始遍历右子树
        cur = cur.right;
    }
    System.out.println(" ");
}

注意代码中，第一次和第二次来到节点 A 的时机，这对于修改成前序、中序以及后序遍历来说非常重要。

Morris 版的前序遍历：

public static void morrisPre(TreeNode root) {
    if (root == null) {
        return;
    }
    TreeNode cur = root;
    TreeNode mostRight;

    while (cur != null) {
        // 这里是 morris 遍历的打印位置
        // System.out.print(cur.value + " ");

        mostRight = cur.left;
        if (cur.left != null) {
            while (mostRight.right != null && mostRight.right != cur) {
                mostRight = mostRight.right;
            }
            if (mostRight.right == null) {
                mostRight.right = cur;
                // 此时是节点 A 第一次找到 mostRight, 同时也是第一次访问节点 A
                // 因为只有在访问到节点 A 时, 才会去寻找其 mostRight
                // 在更新 cur 向左子树遍历前, 先打印一下, 当前打印的顺序是要先于下面 else 里的打印的
                System.out.print(cur.value + " ");
                cur = cur.left;
                continue;
            } else {
                // 此时是节点 A 第二次找到 mostRight, 同时也是第二次访问节点 A,
                // 因为只有在访问到节点 A 时, 才会去寻找其 mostRight
                // 而第二次访问节点 A 后, 出了当前 if 后不会进入到下面的 else, 所以不会打印第二次
                // 从而实现了前序遍历
                mostRight.right = null;
            }
        } else {
            // 第一次来的时候打印
            // 当第二次访问到节点 A 时, 其从上面的寻找 mostRight 的 if 判断中出来后
            // 是无法进入到当前 else 里的, 从而避免了第二次打印节点 A
            // 而对于没有左孩子的节点, 因为根本不会进入上面的 if 里, 所以只会来到这里打印一次
            System.out.print(cur.value + " ");
        }
        cur = cur.right;
    }
    System.out.println(" ");
}

Morris 版的中序遍历：

public static void morrisIn(TreeNode root) {
    if (root == null) {
        return;
    }
    TreeNode cur = root;
    TreeNode mostRight;
    while (cur != null) {
        mostRight = cur.left;
        if (mostRight != null) {
            while (mostRight.right != null && mostRight.right != cur) {
                mostRight = mostRight.right;
            }
            if (mostRight.right == null) {
                mostRight.right = cur;
                cur = cur.left;
                continue;
            } else {
                mostRight.right = null;
            }
        }
        // 中序遍历只需要在这里打印即可, 因为第一次到达节点 A 时, 触发了 continue
        // 导致第一次遍历不会执行到这里, 只有在第二次回到节点 A 时, 走出了上面的 if 后到达这里进行打印
        System.out.print(cur.value + " ");
        cur = cur.right;
    }
    System.out.println(" ");
}

Morris 版的后序遍历：

// Morris 后序遍历的思路:
//    第二次回到节点 A 时, 逆序打印其左子树的所有右侧节点, 所有节点遍历完后, 再逆序打印整棵树的右侧节点
// 解释:
//   不再需要额外打印任何其他节点, 只需要在回到节点 A 时打印其左子树的右侧节点,
//   即可将那些只会遍历一次的节点(没有左孩子)给打印出来, 并且当前节点 A 也会在其祖先节点
//   进行逆序打印时进行打印, 所以整体不漏也不重
// 逆序打印的方法: 不需要栈存储, 直接用链表逆序打印的思路, 将左子树上的右侧节点视为一条链表, 进行逆序打印即可
public static void morrisPos(TreeNode root) {
    if (root == null) {
        return;
    }
    TreeNode cur = root;
    TreeNode mostRight;
    while (cur != null) {
        mostRight = cur.left;
        if (mostRight != null) {
            while (mostRight.right != null && mostRight.right != cur) {
                mostRight = mostRight.right;
            }
            if (mostRight.right == null) {
                mostRight.right = cur;
                cur = cur.left;
                continue;
            } else {
                mostRight.right = null;
                // 只用在第二次回到当前节点时将其左子树上的右侧节点逆序打印
                printEdge(cur.left);
            }
        }
        cur = cur.right;
    }
    // 所有节点遍历完后, 再将整棵树的右侧节点逆序打印
    printEdge(root);
    System.out.println(" ");
}

// 使用递归逆序打印
private static void printEdge(TreeNode cur) {
    if (cur == null) {
        return;
    }
    printEdge(cur.right);
    // 全部孩子都遍历完后再打印自己, 就实现了逆序
    System.out.println(cur.value);
}

直观的理解：每个节点左子树，从右下角向左上角划线逆序打印，整棵树的所有子节点都可以按照这种画法被不漏不重的画出来：

Morris 遍历的应用

Morris 遍历通常用于以较低的空间复杂度遍历整棵树。

应用一：判断某棵树是否是搜索二叉树

思路：使用 Morris 中序遍历，判断当前值是否大于目前的最大值，若不大于，则不是搜索二叉树。

应用二：恢复搜索二叉树

思路：使用 Morris 中序遍历，判断前一个值 pred 是否大于当前值，若大于，则发现了错误点

直观地打印一颗二叉树

public static void printTree(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();
}

几种特殊的二叉树

搜索二叉树

若一棵二叉树根节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值（等于都不行）； 它的左、右子树也分别为搜索二叉树。

搜索二叉树（Binary Search Tree）作为一种经典的数据结构，它既有链表的快速插入与删除操作的特点，又有数组快速查找的优势；所以应用十分广泛，例如在文件系统和数据库系统一般会采用这种数据结构进行高效率的排序与检索操作。

判断一棵树是否是搜索二叉树有三种方法。

方法一：中序遍历后，判断是否升序

一种简单的方法是首先中序遍历这棵二叉树，并在遍历过程中将每个节点的值保存到一个数组里，遍历完成后，再判断该数组是否是升序的。

代码：

public static boolean isSBT01(Node head) {
    List<Integer> list = new ArrayList<>();
    inOrderRecur(head, list);

    // 接着判断数组是否为升序
    for (int i = 0; i < list.size() - 1; i++) {
        if (list.get(i) >= list.get(i+1)) {
            return false;
        }
    }
    return true;
}

public static void inOrderRecur(Node head, List<Integer> list) {
    if (head == null) {
        return;
    }

    inOrderRecur(head.left, list);
    list.add(head.value);
    inOrderRecur(head.right, list);
}

方法二：中序遍历 + 不断保存当前最大值

方法二需要借助一个静态变量 preMaxValue 存储递归过程中 "当前节点之前的所有节点"的最大值 。因为搜索二叉树是按照中序遍历的方式升序的，所以当前节点后面的节点值都要大于该最大值。递归过程中不断保存当前已经遍历过的节点的最大值，并且令后续即将遍历的节点值都要大于该值。

整个方法栈调用时，是先从左下角的那颗子树开始的，按照 左 -> 头 -> 右 的顺序，依次判断当前节点的值是否大于其左侧的所有节点的最大值 preMaxValue，方法栈不断从左下角开始向右上方向扩展，直到整棵树完成遍历：

public static int preMaxValue = Integer.MIN_VALUE;

public static boolean isSBT02(Node head) {
    // 注意这里如果到了边界条件，是返回的true，因为叶子结点必定是满足搜索二叉树条件的
    if (head == null) {
        return true;
    }

    // 先遍历左子树，返回其是否满足搜索二叉树条件
    boolean isLeftBst = isSBT02(head.left);

    // 如果左子树不是搜索二叉树，直接返回false
    if (!isLeftBst) {
        return false;
    }

    // 如果左子树上的点比当前节点的值还要大（或相等），则说明不是搜索二叉树，直接返回false
    if (preMaxValue >= head.value) {
        return false;
    } else {
        // 否则更新最小值为当前节点，令当前节点的右子树上的点都要比该值大
        preMaxValue = head.value;
    }

    // 运行到这里时，当前节点的左子树里的最大值都要比当前节点要小，
    // 说明到这里为止，都是符合搜索二叉树的，接着要遍历当前节点的右子树，判断其是否也满足搜索二叉树
   return isSBT02(head.right);
}

方法三：Morris 中序遍历 + 不断保存当前最大值

与方法二的区别在于使用 Morris 中序遍历节省空间，思路几乎一致。代码：

public static void morrisIn(TreeNode root) {
    if (root == null) {
        return;
    }
    TreeNode cur = root;
    TreeNode mostRight;
    while (cur != null) {
        mostRight = cur.left;
        if (mostRight != null) {
            while (mostRight.right != null && mostRight.right != cur) {
                mostRight = mostRight.right;
            }
            if (mostRight.right == null) {
                mostRight.right = cur;
                cur = cur.left;
                continue;
            } else {
                mostRight.right = null;
            }
        }
        // 中序遍历只需要在这里打印即可, 因为第一次到达节点 A 时, 触发了 continue
        // 导致第一次遍历不会执行到这里, 只有在第二次回到节点 A 时, 走出了上面的 if 后到达这里进行打印
        System.out.print(cur.value + " ");
        cur = cur.right;
    }
    System.out.println(" ");
}

方法四：使用模板套路

先介绍非标准模板的解法

也可以使用模板套路进行解题，每个节点的左右子树都返回一个 ReturnType 对象，其内即保存了该子树上的最大值和最小值，也保存了该子树是否是搜索二叉树。该对象内保存的最小值是给右子树判断时用，最大值是给左子树判断时用。

方法流程：

• 遍历到每一个节点时，首先获取左子树的 ReturnData，判断左子树是否满足搜索二叉树：
  • 如果返回值里的 isBST 为 false，说明其左子树不为搜索二叉树
  • 如果当前节点的值小于等于左子树返回值里的最大值，则说明不是搜索二叉树
  • 如果左子树不满足搜索二叉树，则向上返回一个 new ReturnData(false)，后续的右子树就不会再去判断了，直接方法栈返回到头结点后返回给主程序 false
• 如果左子树满足搜索二叉树，则去获取其右子树的 ReturnData，判断右子树是否满足搜索二叉树：
  • 如果返回值里的 isBST为 false，说明其右子树不为搜索二叉树
  • 如果当前节点的值大于等于右子树返回值里的最小值，则说明不是搜索二叉树
  • 如果右子树不满足搜索二叉树，则向上返回一个 new ReturnData(false)
• 如果左右子树都满足搜索二叉树，则返回一个 ReturnData(leftReturn.min, rightReturn.max)，其内保存了当前子树上的最小值和最大值，其中：
  • 当前子树的最小值是左子树上的最小值
  • 当前子树的最大值是右子树上的最大值

代码：

// 创建模板返回值类，在其内保存当前子树上的最大值和最小值
public static class ReturnData {
    public boolean isSBT = true;
    public int min = Integer.MAX_VALUE;
    public int max = Integer.MIN_VALUE;

    public ReturnData(boolean isSBT) {
        this.isSBT = isSBT;
    }

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

public static boolean isSBT03(Node head) {
    if (head == null) {
        return true;
    }

    ReturnData result = checkIsSBT(head);
    return result.isSBT;
}

public static ReturnData checkIsSBT(Node head) {
    if (head == null) {
        return new ReturnData(true);
    }

    ReturnData leftReturn = checkIsSBT(head.left);

    // 先判断左子树是否满足搜索二叉树：
    //   1. 如果返回值里的 isBST 为 false，说明其左子树不为搜索二叉树
    //   2. 如果当前节点的值小于等于左子树返回值里的最大值，则说明不是搜索二叉树
    if (!leftReturn.isSBT || leftReturn.max >= head.value) {
        return new ReturnData(false);
    }

    ReturnData rightReturn = checkIsSBT(head.right);

    // 再判断右子树是否满足搜索二叉树：
    //   1. 如果返回值里的 isBST 为 false，说明其右子树不为搜索二叉树
    //   2. 如果当前节点的值大于等于右子树返回值里的最小值，则说明不是搜索二叉树
    if (!rightReturn.isSBT || rightReturn.min <= head.value) {
        return new ReturnData(false);
    }

    // 保存当前子树上的最大值和最小值
    // 最小值给右子树判断时用，最大值给左子树判断时用
    // 当前子树上的最小值是左子树上的最小值，最大值是右子树上的最大值
    // 因为其按照中序遍历时是升序大小，说明左子树上的最左叶子结点是最小值，右子树上的最右节点是最大值
    return new ReturnData(leftReturn.min, rightReturn.max);
}

注意：上面这种写法并不是标准的模板套路。标准的模板套路是：只在方法的最后进行 return，在方法前面先调用两个递归获取到左右子树上的返回值，据此进行判断后再最后封装成 ReturnData 返回：

public static ReturnData f(Node head) {
    if (head == null) {
        // 根据具体场景返回相应的值
        return ReturnData(xx, xx, xx);
    }
    
    // 先获取左右子树上的返回值
    ReturnData leftReturnData = f(head.left);
    ReturnData rightReturnData = f(head.right);
    
    // 进行判断处理等，例如将 boolean 类型值设置为 true 或 false，设置最大最小值等
    // ...
    
    // 在最后将设置好的值封装成 ReturnData 并向上返回
    return new ReturnData(xx, xx, xx);
}

在本问题中，使用标准模板的解法：

public static class ReturnData {
    public boolean isSBT = true;
    public int min = Integer.MAX_VALUE;
    public int max = Integer.MIN_VALUE;

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

public static boolean isBST04(Node head) {
    if (head == null) {
        return true;
    }

    ReturnData result = checkBST02(head);
    return result.isSBT;
}

public static ReturnData checkIsSBT02(Node head) {
    if (head == null) {
        return null;
    }

    ReturnData leftReturn = checkIsSBT02(head.left);
    ReturnData rightReturn = checkIsSBT02(head.right);

    boolean isSBT = true;
    // 如果左子树返回值不为空，且左子树不为搜索二叉树，或左子树最大值大于等于当前节点值，说明不构成搜索二叉树
    if (leftReturn != null && (!leftReturn.isSBT || leftReturn.max >= head.value))
        isSBT = false;
    // 如果右子树返回值不为空，且右子树不为搜索二叉树，或右子树最小值小于等于当前节点值，说明不构成搜索二叉树
    if (rightReturn != null && (!rightReturn.isSBT || rightReturn.min <= head.value))
        isSBT = false;

    int min = head.value;
    int max = head.value;
    // 计算左右子树与当前节点构成的子树上的最大值和最小值，返回给上一层节点使用
    if (leftReturn != null) {
        min = Math.min(leftReturn.min, min);
        max = Math.min(leftReturn.max, max);
    }
    if (rightReturn != null) {
        min = Math.min(rightReturn.min, min);
        max = Math.min(rightReturn.max, max);
    }

    return new ReturnData(isSBT, min, max);
}

这种标准模板的方式存在的缺点：一定会遍历整棵树，因为 return 在方法最后，只会在第三次回到该节点时 return，即只有在遍历过当前节点的左右子树后才会 return，这就导致效率相比上面的方式差了一些（上面的方式是只要在左子树上遇到不满足的子树就直接向上返回到根节点，不会再遍历右子树）

搜索二叉树的增删改查操作

搜索二叉树查找节点的流程：

• 如果目标节点值大于当前节点值，则向右递归遍历该树
• 如果目标节点值小于当前节点值，则向左递归遍历该树
• 直到找到当前节点的值等于目标节点值，即找到了目标节点

搜索二叉树插入节点的流程：

• 如果目标节点值大于当前节点值，则向右递归遍历该树
• 如果目标节点值小于当前节点值，则向左递归遍历该树
• 直到遍历到底层时（root == null），即找到了目标节点需要被插入的地方，将其父节点指向目标节点即可（目标节点肯定会被插入到树的某个叶子节点的孩子处）

搜索二叉树删除节点的流程：

• 若目标节点没有左右孩子，说明其是叶子节点，直接将其父节点的对应孩子位置置空（遍历过程中还需要记录当前节点的父节点，需要在删除了目标节点后将其父节点的对应孩子置空）
• 若目标节点有左孩子或右孩子（但不同时存在左右孩子），则将其父节点的对应孩子位置设置为目标节点的左或右孩子即可（让目标节点的孩子代替自己）
• 若目标节点同时有左孩子和右孩子，则找到其右子树上最左的节点或左子树上最右的节点，令该节点代替自己，并且：
  • 若选择右子树的最左节点，则令该节点的父节点的左孩子指向该节点的右子树（令最左节点的右子树代替自己）
  • 若选择左子树的最右节点，则令该节点的父节点的右孩子指向该节点的左子树（令最右节点的左子树代替自己）

完全二叉树

一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树（Complete Binary Tree）。

堆结构即为完全二叉树。

方法一：层次遍历 + 队列

层次遍历常常与队列一起组合出现，因为使用队列先进先出的特点才能保证做到层次遍历，如果是栈结构的先进后出，就无法做到层次遍历

准备一个队列，用于存放层次遍历过程中的每个节点。之所以选择层次遍历，是因为在判断是否满足完全二叉树时有两个判断条件，这两个条件需要依靠层次遍历来实现（因为需要一层一层的遍历，判断当前层内的节点是否满足这两个条件）：

• 当前节点如果只有右孩子，则必定不满足完全二叉树（对应图中情况1）
• 当前节点如果左右孩子不双全，那么当前层所在的后面节点都必须不能有孩子节点，即后面的节点都必须是叶子结点（对应图中情况2）

可以看出，条件2中用到了判断当前层后面节点是否有孩子节点，所以必须使用层次遍历。

对上述两个条件进行解释：

• 如果节点如果只有右孩子，则根据完全二叉树的定义，其必定不符合，因为完全二叉树里有右孩子的话必定得有左孩子
• 当前节点如果左右孩子不双全，那么说明当前节点为临界条件节点，当前层所在的后面节点都必须不能有孩子节点，即后面的节点都必须是叶子结点，这样才满足完全二叉树的定义

代码实现时：

• 条件1较好实现，在遍历过程中添加条件判断即可。
• 条件2的实现则需要借助一个布尔类型的 flag，其在遇到第一个左右孩子不双全的节点（上图中的绿色）时，将 flag = true，并且在每个节点遍历时，判断 flag 的值，如果为 true，就需要额外判断当前节点是否为叶子结点，如果不是则说明不符合完全二叉树。

代码：

public static boolean isCBT(Node head) {
    if (head == null) {
        return true;
    }

    Queue<Node> queue = new LinkedList<>();
    queue.add(head);

    Node left = null;
    Node right = null;
    boolean flag = false;

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

        if (    // 条件1：
                (left == null && right != null)
                ||
                // 条件2：
                (flag == true && (left != null || right != null))) {
            return false;
        }

        if (left != null) {
            queue.add(left);
        }
        if (right != null) {
            queue.add(right);
        }

        // 如果遇到临界条件节点（上文图中绿色节点），则将 flag = true
        if (left == null || right == null) {
            flag = true;
        }
    }

    return true;
}

满二叉树

满二叉树（Full Binary Tree）：除最后一层无任何子节点外，每一层上的所有结点都有两个子结点的二叉树。一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是(2^k) -1 ，则它就是满二叉树。

方法一：层次遍历 + 记录层数与总节点数

判断是否是满二叉树的一种方法是使用层次遍历，在遍历的过程中一边记录层数，一边记录节点个数，遍历结束后判断总节点数和层数的关系是否满足满二叉树条件即可。

public static boolean isFBT01(Node head) {
    if (head == null) {
        return true;
    }

    Queue<Node> queue = new LinkedList<>();
    queue.add(head);

    Map<Node, Integer> layerMap = new HashMap<>();
    layerMap.put(head, 1);

    // 记录当前层
    int curLayer = 0;
    // 记录总节点数
    int count = 0;

    while (!queue.isEmpty()) {
        Node cur = queue.poll();
        count++;
        // 如果 curLayer 小于当前节点的层数，说明需要换层：将层数加一
        // 该判断成立的时机在 遍历到了下一层的第一个节点时
        if (curLayer < layerMap.get(cur))
            curLayer++;

        if (cur.left != null) {
            queue.add(cur.left);
            layerMap.put(cur.left, curLayer + 1);
        }
        if (cur.right != null) {
            queue.add(cur.right);
            layerMap.put(cur.right, curLayer + 1);
        }
    }
    // 判断 count == 2^k - 1
    return count == ((1 << curLayer) - 1);
}

方法二：使用模板套路

判断满二叉树的模板套路非常简单，只需在向左右孩子索要节点数与层数信息，从而更新自己的节点数与层数信息。递归该过程即可得到整棵树的节点数与层数。

代码：

public static class ReturnData {
    public int nodes;
    public int layers;

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

public static boolean isFBT02(Node head) {
    if (head == null) {
        return true;
    }

    ReturnData result = checkIsFull(head);
    return result.nodes == ((1 << result.layers) - 1);
}

public static ReturnData checkIsFull(Node head) {
    if (head == null) {
        return new ReturnData(0, 0);
    }

    ReturnData leftReturn = checkIsFull(head.left);
    ReturnData rightReturn = checkIsFull(head.right);

    // 计算出当前子树的高度和总节点数
    int layers = Math.max(leftReturn.layers, rightReturn.layers) + 1;
    int nodes = leftReturn.nodes + rightReturn.nodes + 1;

    return new ReturnData(nodes, layers);
}

平衡二叉树

平衡二叉树（Balanced Binary Tree）又被称为 AVL 树。它具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

使用模板套路即可解该题，定义 ReturnData 记录子树上的节点个数以及是否是平衡二叉树，不断向上返回时判断即可。

代码：

public static class ReturnData {
    public int nodes;
    public boolean isBBT;
    public ReturnData(boolean isBBT, int data) {
        this.isBBT = isBBT;
        this.nodes = data;
    }
}

public static boolean isBBT(Node head) {
    if (head == null) {
        return true;
    }

    ReturnData result = checkIsBBT(head);

    return result.isBBT;
}

public static ReturnData checkIsBBT(Node head) {
    if (head == null) {
        return new ReturnData(true, 0);
    }

    ReturnData leftReturn = checkIsBBT(head.left);
    ReturnData rightReturn = checkIsBBT(head.right);

    boolean isBBT = true;
    // 如果左右子树表明自己是非平衡二叉树或左右子树的节点数的绝对值之差大于1，则说明当前子树不是平衡二叉树
    if (!leftReturn.isBBT || !rightReturn.isBBT)
        isBBT = false;
    if (Math.abs(leftReturn.nodes - rightReturn.nodes) > 1)
        isBBT = false;

    return new ReturnData(isBBT, Math.max(leftReturn.nodes, rightReturn.nodes) + 1);
}

不使用模板的剪枝操作：

public boolean isBalanced(TreeNode root) {
    return recur(root) != -1;
}

private int recur(TreeNode root) {
    if (root == null) return 0;
    
    int left = recur(root.left);
    // 如果左子树不为平衡二叉树，则直接返回，完成剪枝
    if(left == -1) return -1;
    
    int right = recur(root.right);
    if(right == -1) return -1;
    
    return Math.abs(left - right) < 2 ? Math.max(left, right) + 1 : -1;
}

将有序数组转换为二叉平衡搜索树

给你一个整数数组 nums ，其中元素已经按升序排列，请你将其转换为一棵高度平衡二叉搜索树。高度平衡二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

递归解决：使用递归的方式，每次取数组中间的值比如m作为当前节点，m前面的值作为他左子树的结点值，m后面的值作为他右子树的节点值，示例中一个可能的结果是

每次递归时，左子树对应数组 [start, mid - 1]，右子树对应数组 [mid + 1, end]。注意是没有取到 mid 的，因为 mid 位置的数字已经在当前方法栈中被创建成了一个节点添加到整棵树中，不能将其也放到左右子树的递归里，否则会重复创建节点。

注意边界条件是 start > end。遇到这种情况说明在上一层递归中计算出的 mid 的左侧没有子数组，此时 start == mid，end == mid -1，故其左子树的递归方法里 start > end 。这种情况，说明上一层的 mid 没有了左孩子，因此其左侧递归的结果应该返回 null。

代码：

// 每次取数组中间的数字作为当前节点，其左右子数组作为当前节点的左右树上的节点    
public TreeNode sortedArrayToBST(int[] nums) {
    return sortedArrayToBSTHelper(nums, 0, nums.length - 1);
}

public TreeNode sortedArrayToBSTHelper(int[] nums, int start, int end) {
    // 发生在划分叶子节点时，长度为2的子数组在计算[start, mid - 1] 时
    // 可能出现 start > mid -1 的情况，例如 start == 0, end == 1，则计算出来的
    // mid - 1 == -1 < start; 这种情况说明到了叶子节点，该返回null了
    // 即：上一层递归中计算出的 mid 在左侧没有了子数组，所以其左侧递归的结果应该返回 null
    if (start > end) {
        return null;
    }

    int mid = (start + end) / 2;
    TreeNode root = new TreeNode(nums[mid]);

    // 左侧的范围注意是 [start, mid - 1]
    root.left = sortedArrayToBSTHelper(nums, start, mid - 1);
    root.right = sortedArrayToBSTHelper(nums, mid + 1, end);

    return root;
}

AVL 树原理

二叉树的线索化

定义一个 pre 节点，令其不断等于 node 的前一个节点，在第二次回到当前节点时，设置node的前驱为 pre，然后设置 pre 的后继为 node

代码里的两个条件判断不是同时成立的，一个节点只可能某一个成立

二叉树线索化后，就等于一个双向链表（见书），可以直接按照某种顺序遍历整棵树

自平衡二叉查找树

自平衡二叉查找树又被称为有序表，主要是用它来存储有序的数据

自平衡二叉查找的所有操作的时间复杂度都是 O(logN) 级别。具体实现为：

• 平衡搜索二叉树（BST）系列
  • 平衡二叉树（AVL树）
  • 节点大小平衡树（Size Balanced Tree）
  • 红黑树（Red–Black Tree）
• 跳表（Skip List）

四者的时间复杂度相同。

搜索二叉树的增删改查操作

有序表都是搜索二叉树，因此首先介绍搜索二叉树的增删改查操作。

搜索二叉树查找节点的流程：

• 如果目标节点值大于当前节点值，则向右递归遍历该树
• 如果目标节点值小于当前节点值，则向左递归遍历该树
• 直到找到当前节点的值等于目标节点值，即找到了目标节点

搜索二叉树插入节点的流程：

• 如果目标节点值大于当前节点值，则向右递归遍历该树
• 如果目标节点值小于当前节点值，则向左递归遍历该树
• 直到遍历到底层时（root == null），即找到了目标节点需要被插入的地方，将其父节点指向目标节点即可（目标节点肯定会被插入到树的某个叶子节点的孩子处）

搜索二叉树删除节点的流程：

• 若目标节点没有左右孩子，说明其是叶子节点，直接将其父节点的对应孩子位置置空（遍历过程中还需要记录当前节点的父节点，需要在删除了目标节点后将其父节点的对应孩子置空）
• 若目标节点有左孩子或右孩子（但不同时存在左右孩子），则将其父节点的对应孩子位置设置为目标节点的左或右孩子即可（让目标节点的孩子代替自己）
• 若目标节点同时有左孩子和右孩子，则找到其右子树上最左的节点或左子树上最右的节点，令该节点代替自己，并且：
  • 若选择右子树的最左节点，则令该节点的父节点的左孩子指向该节点的右子树（令最左节点的右子树代替自己）
  • 若选择左子树的最右节点，则令该节点的父节点的右孩子指向该节点的左子树（令最右节点的左子树代替自己）

左旋与右旋

https://blog.csdn.net/blueliuyun/article/details/78523937

如下图所示的操作被称为对节点Q的右旋，对节点P的左旋。二者互为逆操作。即，右旋——自己变为左孩子的右孩子；左旋——自己变为右孩子的左孩子。

AVL 树的自平衡实现原理

AVL 树需要满足某节点的左右子树的高度差不大于1。

当 AVL 插入一个节点或删除一个节点时，从该节点的父节点开始不断向树的顶部遍历，逐个判断当前节点的左右子树是否满足平衡性。如果不满足则开始进行自平衡调整，具体分四种情况：

• LR 型：某个节点的左孩子的右子树 subTree 过长。先进行左旋，然后进行右旋，令该右子树 subTree 的根节点成为该子树的根节点
• LL 型：某个节点的左孩子 A 的左子树过长。只需要进行一次右旋，令该左孩子 A 成为该子树的根节点
• RL 型：某个节点的右孩子的左子树 subTree 过长。先进行右旋，然后进行左旋，令该左子树 subTree 的根节点成为该子树的根节点
• RR 型：某个节点的右孩子的右子树过长。只需要进行一次左旋，令该右孩子 A 成为该子树的根节点

更多细节参考文章：https://zhuanlan.zhihu.com/p/56066942

节点大小平衡树

Size Balanced Tree 也是一种自平衡二叉查找树，它的平衡原理是每棵树的大小，不小于其兄弟树的子树的大小，即每颗叔叔树的大小，不小于其他任何侄子树的大小。

该树的自平衡操作同样借助于左旋和右旋操作，区别在于：

• 四种分型的定义区别：例如，LL 型指当前节点的左孩子的左子树的大小，大于当前节点的右子树的大小。LL 型需要将当前节点进行右旋
• 左右旋的操作和 AVL 树一样
• 左右旋后，递归判断哪些节点的左右孩子变化了，对左右孩子变化了的节点递归进行该过程，直到令所有节点都符合条件
• 与 AVL 树一样，当前子树调整完毕后，继续去其父节点上重复该过程直到整棵树完成自平衡

红黑树

红黑树也是一种自平衡二叉查找树。红黑树的特性：

• 每个节点或者是黑色，或者是红色
• 根节点是黑色
• 每个叶子节点（NIL）是黑色 [注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！]
• 如果一个节点是红色的，则它的子节点必须是黑色的（黑色节点却无此要求）
• 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点（利用该性质实现的平衡性）

二叉树的常见问题

树的序列化与反序列化

剑指 Offer 37. 序列化二叉树：内存里的一棵树如何变成字符串形式，又如何从字符串形式变成内存里的树？两种序列化的方式：

• 前序遍历顺序
• 层次遍历顺序

前序遍历序列化

序列化时，进行前序遍历，如果孩子节点不为空就 append 当前节点的 value，中间以 _ 分割，如果为空需要设置为 #（注意这很关键，需要根据 # 判断何时遇到了 null），。序列化示例： 100_21_37_#_#_#_-42_0_#_#_666_#_#_。

代码：

public static String serialByPre(Node head) {
    StringBuilder builder = new StringBuilder();

    serializeProcessByPre(head, builder);

    return builder.toString();
}

// 序列化时，孩子节点为空需要设置为 #（注意这很关键，需要根据 # 判断何时遇到了 null），
// 不为空就添加数字，中间以 _ 分割
// 序列化示例： 100_21_37_#_#_#_-42_0_#_#_666_#_#_
public static void serializeProcessByPre(Node head, StringBuilder builder) {
    if (head == null) {
        // 遇到空节点，就添加 #，注意，这很重要
        builder.append("#_");
        return;
    }

    // 前序遍历过程中不断将当前节点加入到 builder 里
    builder.append(head.value).append("_");

    serializeProcessByPre(head.left, builder);
    serializeProcessByPre(head.right, builder);
}

前序遍历反序列化

反序列化时，先将序列化后的字符串 split 拆成字符串数组，然后再进行前序遍历，不断创建节点拼接起来，注意遇到 # 说明当前分支到了底，需要返回 null

代码：

public static Node reconByPreString(String serialString) {
    String[] values = serialString.split("_");
    Queue<String> queue = new LinkedList<>();

    for (String value : values) {
        queue.add(value);
    }

    return reconProcess(queue);
}


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

    // 前序遍历时先恢复出当前节点
    Node node = new Node(Integer.parseInt(value));
    node.left = reconProcess(queue);
    node.right = reconProcess(queue);

    return node;
}

层次遍历序列化与反序列化

效果：

代码：

public class Codec {
    public String serialize(TreeNode root) {
        if(root == null) return "[]";
        StringBuilder res = new StringBuilder("[");
        Queue<TreeNode> queue = new LinkedList<>() {{ add(root); }};
        while(!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if(node != null) {
                res.append(node.val + ",");
                queue.add(node.left);
                queue.add(node.right);
            }
            else res.append("null,");
        }
        res.deleteCharAt(res.length() - 1);
        res.append("]");
        return res.toString();
    }

    public TreeNode deserialize(String data) {
        if(data.equals("[]")) return null;
        String[] vals = data.substring(1, data.length() - 1).split(",");
        TreeNode root = new TreeNode(Integer.parseInt(vals[0]));
        Queue<TreeNode> queue = new LinkedList<>() {{ add(root); }};
        int i = 1;
        while(!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if(!vals[i].equals("null")) {
                node.left = new TreeNode(Integer.parseInt(vals[i]));
                queue.add(node.left);
            }
            i++;
            if(!vals[i].equals("null")) {
                node.right = new TreeNode(Integer.parseInt(vals[i]));
                queue.add(node.right);
            }
            i++;
        }
        return root;
    }
}

判断一颗二叉树是不是另一棵二叉树的子树

可以先把两棵树序列化，变成两个字符串，然后 str1.isContain(str2) 直接判断二者是否为包含关系，如果是说明 str2 是 str1 的子树。

求一颗二叉树的最大深度

方法一：递归 + 模板思想

public int maxDepth(Node root) {
    if (root == null) {
        return 0;
    }
    
    // 返回左子树和右子树上最大深度，再加一，即为当前子树的总深度
    return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}

方法二：递归 + 计数

第一次遍历到当前节点时，count++；最后一次回到当前节点时，count–；在遇到叶子节点时再更新一次 maxLayer：

public int maxDepth(Node root) {
    if (root == null) {    
        this.maxLayer = Math.max(this.maxLayer, this.count);
        return this.maxLayer;
    }

    // 第一次来到当前节点时计数加一
    this.count++;

    maxDepth(root.left);
    maxDepth(root.right);
    
    // 最后一次回到当前节点时计数减一
    this.count--;
    return this.maxLayer;
}

方法三：层次遍历 + 计数

使用层次遍历顺序，依次将每一层的节点入队，并且每次遍历一整层的节点，将其左右孩子依次入队，最后再更新一次树的深度。

public int maxDepth(Node root) {
    if (root == null) {
        return 0;
    }

    // 准备队列用于层次遍历
    Queue<Node> queue = new LinkedList<>();
    queue.add(root);
    int maxLayer;

    while (!queue.isEmpty()) {
        int size = queue.size();

        // 将当前队列中存储的节点依次弹出，同时将每个节点的左右孩子都加进去
        while (size-- > 0) {
            Node cur = queue.poll();
            if (cur.left != null)
                queue.add(cur.left);
            if (cur.right != null) 
                queue.add(cur.right);

        }

        // 当前层遍历完成后，更新最大深度
        maxLayer++;   
    }
    return maxLayer;
}

求一颗二叉树的最大宽度

可以在层次遍历的基础上完成该问题的求解。

首先设置几个关键变量：

• maxWidth：要求的目标，整棵二叉树的最大宽度。该值将由最大的nextWidth决定
• nextWidth：当前层的下一层的宽度，将在遍历当前层的孩子节点时不断增大
• curLayer：当前层的编号，用于判断何时开始换层

并且需要一个HashMap用于存储每一个节点的层编号信息。

方法思路：

• 首先将根节点入队，并在HashMap中设置其层数编号为1，初始化三个关键参数都为1
• 弹出队首节点，获取其层数，并与当前层数curLayer对比
  • 若当前层数小于弹出的队首节点，说明该换层了，则将变量进行更新：将下一层宽度nextWidth置空（因为换层后来到的新层还没开始遍历，所以新层的下一层宽度就是0，在后续遍历时才会开始逐渐增加），并更新最大宽度maxWidth
  • 若当前层数等于弹出的队首节点，说明还在当前这一层，不需要做额外操作
• 遍历当前层，获取当前节点的左右孩子，若存在则放入HashMap中，并保存其孩子的层数编号为curLayer + 1，同时将下一层宽度 nextWidth++，因为当前节点的某一个子孩子被遍历到了，所以下一层宽度加一（在最底层时，因为都没孩子节点了，所以 nextWidth 不会增加，这也符合逻辑）
• 重复上面步骤，直到队列为空

其中细节：

• nextWidth保存的是下一层的节点数，其将在换层时，与 maxWidth 对比，为其赋值
• 因为每次对比的时候，给 maxWidth 赋值的都是下一层的宽度，所以在跳到最后一层的第一个节点时，给 maxWidth 附上了最后一层的信息，所以避免了漏层
• 每次更新maxWidth的时机都是在换层时，即遍历到下一层的第一个节点时，将原本下一层的宽度值 nextWidth（该值在其上一层遍历左右孩子的时候就已经被更新了，所以这里可以直接获取到，相当于提前更新了下一层的节点数）与当前最大宽度 maxWidth 对比并赋值。

方法思想：层次遍历。提前计算好下一层的最大宽度，在换层时直接提前赋值给 maxWidth ，避免了漏层。

代码：

public static void getTreeMaxWidth(Node head) {
    if (head == null) {
        return;
    }

    int maxWidth = 1;
    int nextWidth = 1;
    int curLayer = 1;
    Map<Node, Integer> map = new HashMap<>();
    Queue<Node> queue = new LinkedList<>();
    queue.add(head);
    map.put(head, 1);

    while (!queue.isEmpty()) {
        Node cur = queue.poll();
        // 如果当前层数小于出队的节点的层数，说明该换层了
        // 换层时，将下一层宽度置空 nextWidth = 0，并更新最大宽度
        if (curLayer < map.get(cur)) {
            maxWidth = Math.max(nextWidth, maxWidth);
            curLayer++;
            nextWidth = 0;
        }

        // 注意：nextWidth 记录的是下一层的节点数
        if (cur.left != null) {
            queue.add(cur.left);
            // 左右孩子对应的层数是当前层数+1
            map.put(cur.left, curLayer+1);
            nextWidth++;
        }
        if (cur.right != null) {
            queue.add(cur.right);
            map.put(cur.right, curLayer+1);
            nextWidth++;
        }
    }

    System.out.println("max with = " + maxWidth);
}

层次遍历优化

可以对上述代码进行优化。层次遍历时，可以进行双层 while 循环，外层循环判断当前树的节点是否全部都遍历过，内层循环则负责循环当前层的所有节点。

具体做法为：在内层 while 循环开始遍历前，首先计算当前队列内的节点个数。这个数字，其实就是目前队列中当前层节点的个数。

原因：在内层 while 循环里，每次都将当前层的所有节点依次弹出，同时把其左右孩子都入队，这就导致了，第 N 层的 M 个节点都遍历后，队列里就 add 了第 N+1 层的所有节点，这样再进入下一次外层的 while 循环后，再次计算队列里的节点个数时，得到的数量就是第 N+1 层的节点个数。

利用这种思想，可以一次性遍历一整层的节点，从而十分方便地计算当前层宽度

记得当每进入一次外层循环时就令 count = 0，在每一次外层循环即将结束，更新 maxWidth

优化后代码：

public static int getTreeMaxWidth3(Node head) {
    if (head == null)
        return 0;

    Queue<Node> queue = new LinkedList<>();
    queue.add(head);
    int maxWidth = 0;
    int count = 0;

    while (!queue.isEmpty()) {
        // 首先别忘了将当前层节点个数清空
        count = 0;

        int size = queue.size();
        // 依次遍历当前层内所有节点
        while (size-- > 0) {
            Node cur = queue.poll();
            if (cur.left != null)
                queue.add(cur.left);
            if (cur.right != null)
                queue.add(cur.right);
            // 每遍历一个当前层的节点，就更新一次最大宽度
            count++;
        }
        // 每遍历一次当前层节点，就更新一次最大宽度
        maxWidth = Math.max(maxWidth, count);
    }
    return maxWidth;
}

重建二叉树

输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

思路：

• 先将中序数组里的所有数字及其对应的索引都加入到一个哈希表中，用于快速查询到前序数组中某个根节点在中序数组中的位置，从而根据该位置将中序数组划分为左右两半
• 递归方法传入参数：
  • preRoot：前序数组中当前子树的根节点的索引值，使用该值创建出树结构，并去中序哈希表里查找该根节点在中序数组中的位置
  • inleft, inright：中序数组中当前子树的左右边界索引值，代表当前子树包含的节点只可能在此区间内
• 根据传入的 preRoot 创建出对应的树节点，然后利用中序哈希表定位到该节点在中序数组中的位置 i，并据此将中序数组划分为左右两个区间：
  • 中序数组中左子树的范围：[inleft, i - 1]
  • 中序数组中右子树的范围：[i + 1, inright]
• 根据划分出来的左右子树范围，计算出当前节点的左右子树的根节点（新一轮递归中的根节点）在前序数组中的位置：
  • preRoot 的左子树的根节点：preRoot + 1
  • preRoot 的左子树的根节点：preRoot + leftLength + 1 = preRoot + i - inleft + 1
• 使用计算出的新根节点位置（在前序数组中）以及新根节点的左右边界范围（在中序数组中）进行递归，直到 left > right 时递归返回。

代码：

class Solution {
    Map<Integer, Integer> inorderMap;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        // inorder 先存储到哈希表中
        this.inorderMap = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            // 存储每个元素值以及其对应的下标，用于快速定位该元素
            inorderMap.put(inorder[i], i);
        }
        return buildTreeHelper(preorder, 0, 0, inorder.length - 1);
    }

    public TreeNode buildTreeHelper(int[] preorder, int preRoot, int inleft, int inright) {
        // 如果中序数组的左边界大于右边界，则不能继续递归了
        if (inleft > inright) {
            return null;
        }

        TreeNode curRoot = new TreeNode(preorder[preRoot]);
        // 从中序哈希表中找出当前根节点的位置
        int i = this.inorderMap.get(preorder[preRoot]);

        // 前序数组中左子树的根节点为 preRoot + 1
        // 中序数组中左子树的范围：[inleft, i - 1]
        curRoot.left = buildTreeHelper(preorder, preRoot + 1, inleft, i - 1);
        // 左子树的长度为：i-1 - left + 1
        int leftLength = i - inleft;
        // 前序数组中右子树的根节点为 preRoot + leftLength + 1
        // 中序数组中右子树的范围：[i + 1, inright]
        curRoot.right = buildTreeHelper(preorder, preRoot + leftLength + 1, i + 1, inright);

        return curRoot;
    }
}

二叉搜索树的最近公共祖先

本题给定了两个重要条件：

• 树为二叉搜索树
• 树的所有节点的值都是唯一的。

根据以上条件，可方便地判断 p，q 与 root 的子树关系，即：

• 若 root.val < p.val，则 p 在 root 右子树 中；
• 若 root.val > p.val，则 p 在 root 左子树 中；
• 若 root.val = p.val，则 p 和 root 指向同一节点 。

方法一：迭代

循环搜索： 当节点 root 为空时跳出；

• 当 p，q 都在 root 的右子树中，则遍历至 root.right
• 否则，当 p，q 都在 root 的左子树中，则遍历至 root.left
• 否则，说明找到了最近公共祖先，跳出

代码：

// 迭代版本
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    while (true) {
        if (root.val < p.val && root.val < q.val) {
            // p,q 在 root 的右子树
            root = root.right;
        } else if (root.val > p.val && root.val > q.val) {
            // p,q 在 root 的左子树
            root = root.left;
        } else {
            break;
        }
    }
    return root;
}

方法二：递归

递推工作：

• 当 p，q 都在 root 的右子树中，则开启递归 root.right 并返回；
• 否则，当 p，q 都在 root 的左子树中，则开启递归 root.left 并返回；

返回值：最近公共祖先 root 。

代码：

// 递归版本
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if(root.val < p.val && root.val < q.val)
        return lowestCommonAncestor(root.right, p, q);
    if(root.val > p.val && root.val > q.val)
        return lowestCommonAncestor(root.left, p, q);
    return root;
}

二叉树的最低公共祖先

方法一：递归

本题是普通的树，而非二叉搜索树，因此不能简单的判断当前节点值是否小于或大于p，q的值。而应该在递归过程中判断当前节点的值是否等于 p 或 q：

• 如果当前节点为空，则返回 null
• 若相等，则找到了二者中的某一个，直接向上返回该节点（如果是 p 是 q 的祖先的情况，则此时返回的就是二者中更靠上层的节点，也就是另一个节点的最近祖先）
• 若不相等，则继续递归向下寻找是够有节点等于 p 或 q

递归方法的返回值共有四种情况：

• 如果 left，right 都为空，则当前子树上不包含二者，直接返回 null
• 如果二者都不为空，则当前 root 即为二者的最近公共祖先，返回 root（root 就是左右子树上的 p 和 q 的公共祖先节点）
• 如果左子树为空，右子树不为空，则右子树上有 p 或 q（或者都有），左子树上肯定没有 p 和 q，返回 right（right 就是右子树递归向下寻找到的那个等于 p 或 q 的节点，或者是二者的某个祖先节点，该节点被一路向上返回，直到得到答案）
• 如果右子树为空，左子树不为空，则左子树上有 p 或 q（或者都有），右子树上肯定没有 p 和 q，返回 left

图解该过程：

代码：

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    // base case，到底时返回null
    if (root == null || p == null || q == null) {
        return null;
    }
    if (p.val == root.val) {
        return root;
    } else if (q.val == root.val) {
        return root;
    }

    TreeNode left = lowestCommonAncestor(root.left, p, q);
    TreeNode right = lowestCommonAncestor(root.right, p, q);
    // 共有四种情况
    // 1. left,right 都为空，则当前子树上不包含二者，直接返回null
    if (left == null && right == null) {
        return null;
    }
    // 2. 如果二者都不为空，则当前root即为二者的最近公共祖先，返回root
    if (left != null && right != null) {
        return root;
    }
    // 3. 如果左子树为空，右子树不为空，则右子树上有p或q（或者都有），左子树上肯定没有p和q，返回right
    if (left == null && right != null) {
        return right;
    }
    // 4. 如果右子树为空，左子树不为空，则左子树上有p或q（或者都有），右子树上肯定没有p和q，返回left
    if (right == null && left != null) {
        return left;
    }
    // 应该不会来到这里的
    return null;
}

方法二：哈希表记录每个节点的父节点

思路：

1. 第一次遍历二叉树时，使用一个 HashMap 存放每个节点的头节点
2. 然后借助于第一步获取的 HashMap 遍历 o1 的祖先节点们，使用一个 HashSet 存放 o1 节点的祖先节点（注意要包含 o1 自身）
3. 最后遍历 o2 的祖先节点们，判断当前节点是否在第二步创建的 HashSet 里（注意要包含 o2 自身），如果在，说明该节点就是二者的最低公共祖先

需要注意步骤2,3里存储 o1 的祖先节点时需要将 o1 自身也存进去，遍历 o2 的祖先节点时需要将 o2 也进行判断。这是为了在 o1、o2 在同一条链上时不会漏掉 o1 或 o2 自身。

代码：

public static Node lowestCommonAncestor(Node head, Node o1, Node o2) {
    // 先将头结点自身添加到 map 中，设置头结点为自己
    Map<Node, Node> fatherMap = new HashMap<>();
    fatherMap.put(head, head);

    process(head, fatherMap);

    Set<Node> set1 = new HashSet<>();
    Node cur = o1;

    // 先将自身添加到 set1 里，避免 o1 就是 o2 祖先节点时漏放 o1 造成出错
    // 注意：必须要把 o1 自身也加到 Set 里，不然如果出现 o1 和 o2 在同一条链上（例如 o1 是 o2 的祖先）的情况下
    // 如果 o1 自身没加到 Set 里，o2 在找祖先节点时就会漏掉 o1
    set1.add(o1);

    // 从 o1 开始向上沿着自己的父节点遍历，直到找到根节点 head（因为只有 head 的 father 等于自身）
    while (cur != fatherMap.get(cur)) {
        // 先找到 cur 的父节点
        // 然后不断将 o1 的祖先结点们添加到 set1 中，直到最后将 head 添加进去
        cur = fatherMap.get(cur);
        set1.add(cur);
    }
    // 上面那种顺序就不再需要将 head 添加到 set1 中，因为在临界条件时就已经加进去了
    // set1.add(head);

    cur = o2;
    // 开始遍历 o2 的祖先节点们（注意，遍历时要包括 o2 自己）
    while (cur != fatherMap.get(cur)) {
        // 下面两句顺序不能反，必须先判断当前节点在不在 set1 里，因为可能 o2 就是其中的某一个节点
        // 如果顺序反了，就漏掉了 o2
        if (set1.contains(cur))
            return cur;
        cur = fatherMap.get(cur);
    }

    return null;
}

public static void process(Node head, Map<Node, Node> fatherMap) {
    if (head == null) {
        return;
    }

    // 将当前节点的左右孩子节点添加到 map 中
    if (head.left != null)
        fatherMap.put(head.left, head);
    if (head.right != null)
        fatherMap.put(head.right, head);

    // 递归，令子节点也添加自己的左右孩子节点到 map 中
    process(head.left, fatherMap);
    process(head.right, fatherMap);
}

寻找二叉树的后继节点

方法一：中序遍历 + 存储节点到 List 中

简单的想法是在中序遍历的过程中将每个节点保存到一个 List 中，然后再在该 List 里找到其下一个节点即为其后继节点。但是代价是时间复杂度为 O(N)，并且空间复杂度也为 O(N)。

方法二：借助父节点

如果已知每一个节点的父节点，那么其实目标节点寻找距离自己 K 单位的后继节点所耗费的时间复杂度可以优化到 O(K)。

共有三种情况：

• 目标节点有右孩子：此时目标节点的右孩子所在的右子树上最左边的节点就是当前节点的后继节点，对应下图中的情况1
• 目标节点没有右孩子：则一直向上遍历他的父节点，直到当前节点是其父节点的左孩子，则这个父节点就是目标节点的后继节点，对应下图中的情况2
• 目标节点是整棵树最右侧的节点：其后继节点为 null，对应下图中的情况2中的黄色节点

图解：

代码：

// 传参只需要待求的节点
public static Node getSuccessorNode(Node node) {
    if (node == null)
        return null;

    // 1. 如果目标节点有右孩子，则右孩子所在的右子树上最左边的节点就是 node 的后继节点
    if (node.right != null) {
        return getLeftMostNode(node.right);
    }

    // 2. 如果目标节点没有右孩子，则一直向上遍历他的父节点，直到当前节点是其父节点的左孩子
    //    这种情况对应了 while 循环里的第二条判断条件，当其满足时即找到了后继节点
    // 3. 同样包括了第三种情况：node 为整棵树最右的那个节点，其后继节点为 null，
    //    这种情况对应了 while 循环里的第一条判断条件，当其满足时，node 就是 head，最后 return head.parent == null
    while (node.parent != null && node != node.parent.left) {
        node = node.parent;
    }
    // 注意要返回的是 parent 而不是 node，因为他跳出 while 循环时，node 是要求的后继节点的左孩子
    // 需要返回 node.parent
    return node.parent;
}

// 寻找子树上的最左节点，不需要递归，直接一直找左孩子即可
public static Node getLeftMostNode(Node node) {
    if (node == null) {
        return null;
    }

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

翻转二叉树

翻转的本质是：交换每个节点的左右孩子。

方法一：递归 + 交换左右孩子

在递归时，不断交换当前节点的左右孩子节点，如此下去，最后就完成了整棵树的翻转。

代码：

public Node invertTree(Node root) {
    //递归函数的终止条件，节点为空时返回
    if(root == null) {
        return null;
    }
    //下面三句是将当前节点的左右子树交换
    Node tmp = root.right;
    root.right = root.left;
    root.left = tmp;
    //递归交换当前节点的 左子树
    invertTree(root.left);
    //递归交换当前节点的 右子树
    invertTree(root.right);
    //函数返回时就表示当前这个节点，以及它的左右子树
    //都已经交换完了
    return root;
}

方法二：层次遍历 + 交换左右孩子

也可以使用层次遍历。在层次遍历的过程中，先将当前节点的左右孩子进行交换，然后再放入队列中。

代码：

public Node invertTree(Node root) {
    if(root==null) {
        return null;
    }
    //将二叉树中的节点逐层放入队列中，再迭代处理队列中的元素
    LinkedList<Node> queue = new LinkedList<>();
    queue.add(root);
    while(!queue.isEmpty()) {
        //每次都从队列中拿一个节点，并交换这个节点的左右子树
        Node tmp = queue.poll();
        Node left = tmp.left;
        tmp.left = tmp.right;
        tmp.right = left;
        //如果当前节点的左子树不为空，则放入队列等待后续处理
        if(tmp.left!=null) {
            queue.add(tmp.left);
        }
        //如果当前节点的右子树不为空，则放入队列等待后续处理
        if(tmp.right!=null) {
            queue.add(tmp.right);
        }
    }
    //返回处理完的根节点
    return root;
}

该方法的空间复杂度会比第一种方法更大。

对称的二叉树

https://leetcode-cn.com/problems/dui-cheng-de-er-cha-shu-lcof/

请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

思路：递归时每次传入一对节点（这两个节点是位置对称的），例如传入 L.left 和 R.right；另一个递归方法传入 L.right 和 R.left。这样保证每次递归方法里的节点都是位置对称的，因此只需要判断这两个节点的值是否相同即可。

代码：

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        return recur(root.left, root.right);
    }

    public boolean recur(TreeNode leftSubTree, TreeNode rightSubTree) {
        // 1. 判断 leftSubTree ?= rightSubTree

        // 这两个判断不需要在当前层进行，将会在下一层进行比较
        // 2. 判断 leftSubTree.left ?= rightSubTree.right
        // 3. 判断 leftSubtree.right ?= rightSubTree.left 
        
        // 一对一对的递归，递归时判断这一对是不是对称的
        // 如果所有对都是对称的，整体就是对称的

        if (leftSubTree == null || rightSubTree == null) {
            return leftSubTree == rightSubTree ? true : false;
        }
		
        // 判断当前的这一对对称位置的节点是否值相等
        if (leftSubTree.val != rightSubTree.val) {
            return false;
        }

        // 将两对对称的节点继续递归
        return recur(leftSubTree.left, rightSubTree.right) && recur(leftSubTree.right, rightSubTree.left);
    }
}

树的子结构

https://leetcode-cn.com/problems/shu-de-zi-jie-gou-lcof/solution/mian-shi-ti-26-shu-de-zi-jie-gou-xian-xu-bian-li-p/

输入两棵二叉树A和B，判断B是不是A的子结构。（约定空树不是任意一个树的子结构）

B是A的子结构， 即A中有出现和B相同的结构和节点值。

思路：双递归，一个递归寻找A中哪个节点与B树的根节点相同；另一个递归在找到相同的节点后开始深入A的当前局部子树进行递归。示意图：

算法流程：

名词规定：树 A*A* 的根节点记作 节点 A*A* ，树 B*B* 的根节点称为 节点 B*B* 。

recur(A, B) 函数：

• 终止条件：
  • 当节点 B 为空：说明树 B 已匹配完成（越过叶子节点），因此返回 true
  • 当节点 A 为空：说明已经越过树 A 叶子节点，即匹配失败，返回 false
  • 当节点 A 和 B 的值不同：说明匹配失败，返回 false
• 返回值：
  • 判断 A 和 B 的左子节点是否相等，即 recur(A.left, B.left)
  • 判断 A 和 B 的右子节点是否相等，即 recur(A.right, B.right)

isSubStructure(A, B) 函数：

• 特例处理： 当 树 A 为空 或 树 B 为空 时，直接返回 false
• 返回值： 若树 B 是树 A 的子结构，则必满足以下三种情况之一，因此用或 || 连接
  • 以 节点 A 为根节点的子树 包含树 BB ，对应 recur(A, B)
  • 树 B 是 树 A 左子树 的子结构，对应 isSubStructure(A.left, B)
  • 树 B 是 树 A 右子树 的子结构，对应 isSubStructure(A.right, B)

以上 2. 3. 实质上是在对树 AA 做 先序遍历 。

复杂度分析：

• 时间复杂度 O(MN) ： 其中 M,N 分别为树 A 和 树 B 的节点数量；先序遍历树 A 占用 O(M) ，每次调用 recur(A, B)判断占用 O(N) 。
• 空间复杂度 O(M)： 当树 A 和树 B 都退化为链表时，递归调用深度最大。当 M ≤ N 时，遍历树 A 与递归判断的总递归深度为 M ；当 M>N 时，最差情况为遍历至树 A 叶子节点，此时总递归深度为 M。

代码：

// 题解：简洁形式
public boolean isSubStructure(TreeNode A, TreeNode B) {
    return (A != null && B != null) && (recur(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B));
}

boolean recur(TreeNode A, TreeNode B) {
    // 如果B为空，说明B遍历到底了，当前分支下是相同的子结构，递归返回开始判断其他分支是否也是相同子结构
    if(B == null) return true;
    // 如果B不为空，但A为空；或者B和A的值不同，说明B不是A的子结构
    if(A == null || A.val != B.val) return false;
    // 只有在左子树和右子树都为true才说明整体也是true
    return recur(A.left, B.left) && recur(A.right, B.right);
}

// 我自己的：
public boolean isSubStructure(TreeNode A, TreeNode B) {
    if(A == null || B == null){
        return false;
    }
    boolean res = false;

    // 注意是判断 值 是否相同，而不是节点是否相同
    // 并且注意，不能直接返回！！因为可能目标位置很靠下，在书的上层就有一个A和值和B的值相同，如果在这里就返回了，就会漏掉下面的正确结构，直接返回false了，就错误了
    if (A.val == B.val) {
        res |= f(A, B);
    }    
    res |= isSubStructure(A.left, B);
    res |= isSubStructure(A.right, B);
    return res;
    // 上面这几行也可以写成：
    // 1. 当前A位置组成的子树是否包含B树 || 2. 当前左子树是否包含B树 || 3. 当前右子树是否包含B树
    return f(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
    // 按照树形DP的模板套路可以理解为：
    //    1. 考虑当前节点A的情况：f(A, B)
    //    2. 不考虑当前节点A的情况：
    //       2.1 左子树是否满足 isSubStructure(A.left, B)
    //       2.2 右子树是否满足 isSubStructure(A.right, B)  
        
    // 再精简一下就是：    
    // return (A != null && B != null) && (recur(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B));
}

public boolean f(TreeNode a, TreeNode b) {
    // a为空说明走到底了，但是b又不为空，说明不是子结构返回false
    if (a == null) {
        return false;
    }

    // 二者如果不相等，说明肯定不是子结构（因为b能进这层循环就不为空，a经过前面判断也不为空，则说明a和b都有值也不相等，则不是子结构）
    if (a.val != b.val) {
        return false;
    }

    boolean res = true;

    if (b.left != null) {
        res &= f(a.left, b.left);
    } 
    if (b.right != null) {
        res &= f(a.right, b.right);
    }
    return res;
}

二叉树中和为某一值的路径

剑指 Offer 34. 二叉树中和为某一值的路径：给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有从根节点到叶子节点 路径总和等于给定目标和的路径。叶子节点是指没有子节点的节点。

方法一：深度优先遍历

• 前序遍历： 按照 “根、左、右” 的顺序，遍历树的所有节点。
• 路径记录： 在先序遍历中，记录从根节点到当前节点的路径。当路径为 ① 根节点到叶节点形成的路径 且 ② 各节点值的和等于目标值 sum 时，将此路径加入结果列表。

注意：记录路径时若直接执行 res.append(path) ，则是将 path 对象加入了 res ；后续 path 改变时， res 中的 path 对象也会随之改变。正确做法：res.append(list(path)) ，相当于复制了一个 path 并加入到 res 。

List<List<Integer>> res = new LinkedList<List<Integer>>();
Deque<Integer> path = new LinkedList<Integer>();

public List<List<Integer>> pathSum(TreeNode root, int target) {
    dfs(root, target);
    return ret;
}

public void dfs(TreeNode root, int target) {
    if (root == null) {
        return;
    }
    // 先添加当前节点的值，代表来过当前节点
    path.offerLast(root.val);
    // 更新target
    target -= root.val;
    // 如果当前节点时叶子节点，且 target == 0，则找到了一条符合题意的分支，进行保存
    // 注意！！！保存时需要另外复制一份path，否则path其随着方法栈返回会被修改
    if (root.left == null && root.right == null && target == 0) {
        res.add(new LinkedList<Integer>(path));
    }
    dfs(root.left, target);
    dfs(root.right, target);
    // 左右子树遍历完后，记得删掉之前添加的值
    path.pollLast();
}

方法二：广度优先搜索

也可以采用广度优先搜索的方式遍历这棵树。当我们遍历到叶子节点，且此时路径和恰为目标和时，我们就找到了一条满足条件的路径。

为了节省空间，我们使用哈希表记录树中的每一个节点的父节点。每次找到一个满足条件的节点，我们就从该节点出发不断向父节点迭代，即可还原出从根节点到当前节点的路径。

代码：

List<List<Integer>> ret = new LinkedList<List<Integer>>();
Map<TreeNode, TreeNode> map = new HashMap<TreeNode, TreeNode>();

public List<List<Integer>> pathSum(TreeNode root, int target) {
    if (root == null) {
        return ret;
    }

    Queue<TreeNode> queueNode = new LinkedList<TreeNode>();
    Queue<Integer> queueSum = new LinkedList<Integer>();
    queueNode.offer(root);
    queueSum.offer(0);

    while (!queueNode.isEmpty()) {
        TreeNode node = queueNode.poll();
        int rec = queueSum.poll() + node.val;

        if (node.left == null && node.right == null) {
            if (rec == target) {
                getPath(node);
            }
        } else {
            if (node.left != null) {
                map.put(node.left, node);
                queueNode.offer(node.left);
                queueSum.offer(rec);
            }
            if (node.right != null) {
                map.put(node.right, node);
                queueNode.offer(node.right);
                queueSum.offer(rec);
            }
        }
    }

    return ret;
}

public void getPath(TreeNode node) {
    List<Integer> temp = new LinkedList<Integer>();
    while (node != null) {
        temp.add(node.val);
        node = map.get(node);
    }
    Collections.reverse(temp);
    ret.add(new LinkedList<Integer>(temp));
}

二叉搜索树的后序遍历序列

剑指 Offer 33. 二叉搜索树的后序遍历序列：输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。

解决该问题的关键在于理解后序遍历在数组中的体现：

• 根节点位置：后序遍历：在数组的最后一个位置
• 左右子树的分布特点：后序遍历：左 -> 右 -> 根

因此重点在于如何确定左右子树间的边界。

方法一：递归分治

一种思路是：根据二叉搜索树的特点，左子树区间内的值都应该小于当前根节点值，右子树区间内的值都应该大于当前根节点值。那么从左往右遍历一遍数组，定位到：第一个大于根节点值的位置 m，则 [left, m - 1] 为左子树区间；[m, right - 1] 为右子树区间。然后继续在右子树区间内遍历，直到与 right 位置相遇。如果无法相遇则代表当前子树不符合；如果可以相遇则代表当前子树符合，那么接着开始递归判断左子树 [left, m - 1] 是否符合，右子树 [m, right - 1] 是否符合。

示意图：

代码：

class Solution {
    public boolean verifyPostorder(int[] postorder) {
        return recur(postorder, 0, postorder.length - 1);
    }

    public boolean recur(int[] postorder, int left, int right) {
        if (left >= right) {
            return true;
        }

        // 当前子树的范围[left, right]，因为是后序遍历，所以当前子树的根节点必定是postorder[right]的值，
        int i = left;
        // 一直遍历到第一个大于postorder[right]的位置m，m-1就是当前根节点的左子树的根节点（子数组里的右边界right）
        // 1. 当前遍历的是左子树
        while (postorder[i] < postorder[right]) {
            i++;
        }
        // 记录一下第一个大于根节点值的位置，该位置理论上来说是右子树的左边界（最左结点），m-1是左子树的右边界
        int m = i;
        // 2. 接着遍历右子树，如果是符合二叉搜索树，则肯定是都比rootValue大的，那么就能一直遍历到right
        while (postorder[i] > postorder[right]) {
            i++;
        }
        // 如果i != right，则i没有能顺利遍历到right位置，说明肯定不是二叉搜索树（否则肯定能遍历到right位置）
		// 如果i == right，则当前以postorder[right]为根节点的子树是符合二叉搜索树的，接着开始递归判断该树的左右子树是否也是满足的
        // 根节点：right  左子树范围：[left, m - 1]，右子树范围：[m, right - 1]
        return i == right && recur(postorder, left, m - 1) && recur(postorder, m, right - 1);
    }
}

方法二：单调栈

方法三：倒序重建

可以尝试倒序重建整棵二叉树，如果重建过程中发现不符合就返回 false。当然不是重建出整棵树的结构，而是判断当前根节点（当前子数组的最后一个节点）是否在合适区间内：

• 当前根节点的右子树的根节点的值应该大于当前的值且小于最大值
• 当前根节点的左子树的根节点的值应该小于当前的值且大于最小值

参考的 python 代码：

class Solution:
    def verifyPostorder(self, postorder: List[int]) -> bool:
        def build(postorder: List[int], ma: int, mi: int):
            if not postorder: return
            val = postorder[-1]
            if not mi < val < ma: return
            postorder.pop() # 根
            build(postorder, ma, val) # 右
            build(postorder, val, mi) # 左

        build(postorder, sys.maxsize, -sys.maxsize)
        return not postorder

填充每个节点的下一个右侧节点指针 II

117. 填充每个节点的下一个右侧节点指针 II：给定一个二叉树，填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

思路：一旦在某层的节点之间建立了 next 指针，那这层节点实际上形成了一个链表。因此，如果先去建立某一层的 next 指针，再去遍历这一层，就无需再使用队列了。基于该想法，提出降低空间复杂度的思路：如果第 i 层节点之间已经建立 next 指针，就可以通过 next 指针访问该层的所有节点，同时对于每个第 i 层的节点，我们又可以通过它的 left 和 right 指针知道其第 i+1 层的孩子节点是什么，所以遍历过程中就能够按顺序为第 i + 1 层节点建立 next 指针。

具体来说：

• 从根节点开始。因为第 0 层只有一个节点，不需要处理。可以在上一层为下一层建立 next 指针。该方法最重要的一点是：位于第 x 层时为第 x + 1 层建立 next 指针。一旦完成这些连接操作，移至第 x + 1 层为第 x + 2 层建立 next 指针。
• 当遍历到某层节点时，该层节点的 next 指针已经建立。这样就不需要队列从而节省空间。每次只要知道下一层的最左边的节点，就可以从该节点开始，像遍历链表一样遍历该层的所有节点。

在代码实现时，需要设置两重循环：

• 最外层 while(cur != null) 判断何时遍历完整棵树
• 内层的 for (; cur != null; cur = cur.next) 判断何时遍历完当前层
• 在每层遍历完后，更新 cur 为下一层的开始：cur = nextLayerFirstNode
• 在每一层开始遍历前，都先重置 lastNode = null 以及 nextLayerFirstNode = null

代码：

class Solution {
    Node lastNode = null;
    Node nextLayerFirstNode = null;

    public Node connect(Node root) {
        if (root == null) {
            return root;
        }
        Node cur = root;
        // 总循环，退出时整棵树遍历完毕
        while (cur != null) {
            // 每一层都需要初始化
            lastNode = null;
            nextLayerFirstNode = null;

            // 内层循环，遍历每一层，退出时这一层遍历完毕
            for (; cur != null; cur = cur.next) {
                if (cur.left != null) {
                    handle(cur.left);
                }   
                if (cur.right != null) {   
                    handle(cur.right);
                }
            }
            // 使用这一层最开始的节点记录的 nextLayerFirstNode 信息遍历到下一层
            cur = nextLayerFirstNode;
        }
        return root;
    }
	
    // 注意，lastNode 必须在类成员变量更新，而不能作为形参，否则会局部更新，全局无效
    public void handle(Node cur) {
        if (lastNode == null) {
            // 此时是下一层的第一个节点
            nextLayerFirstNode = cur;
        } else {
            // 和前面的节点连接起来
            lastNode.next = cur;
        }
        // 更新下一层的最后一个位置
        lastNode = cur;
    }
}

从上到下打印二叉树 III

剑指 Offer 32 - III. 从上到下打印二叉树 III：请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。

有三种方法可以解决该问题：

• 仍然按照原顺序（从左到右）打印，只不过在每一层保存结果到 list 中时，使用 LinkedList 按照奇偶层选择 addFirst() 还是 addLast() 添加到 当前层的 tmp 链表里。该方法无法实现真正的之字形打印，只是保证了答案链表里的顺序
• 使用双端队列，每次遍历连续的奇、偶两层：
  • 在奇数层：removeFirst() 获取当前节点。addLast() 先左孩子再右孩子
  • 在偶数层：removeLast() 获取当前节点。addFirst() 先右孩子再左孩子
• 使用两个栈，一个栈存储奇数层的，一个栈存储偶数层的
  • 遍历奇数层时，向偶数栈中压入当前层的孩子；先左后右
  • 遍历偶数层时，向奇数栈中压入当前层的孩子；先右后左

代码：

// 方法一：
public List<List<Integer>> levelOrder(TreeNode root) {
    if (root == null) {
        return new ArrayList<>();
    }
    List<List<Integer>> ans = new ArrayList<>();
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    TreeNode cur = null;
    while (!queue.isEmpty()) {
        int size = queue.size();
        // 注意类型必须为 LinkedList，否则没有 addFirst() 方法
        LinkedList<Integer> tmp = new LinkedList<>();
        while (size-- > 0) {
            cur = queue.poll();
            // 奇数层
            if (ans.size() % 2 == 0) {
                tmp.addLast(cur.val);
            } else {
                // 偶数层
                tmp.addFirst(cur.val);
            }
            if (cur.left != null) {
                queue.add(cur.left);
            }
            if (cur.right != null) {
                queue.add(cur.right);
            }
        }
        ans.add(tmp);
    }

    return ans;
}

// 方法二：双端队列
public List<List<Integer>> levelOrderDeque(TreeNode root) {
    Deque<TreeNode> queue = new LinkedList<>();
    List<List<Integer>> res = new ArrayList<>();
    queue.addFirst(root);

    while (!queue.isEmpty()) {
        int size = queue.size();
        List<Integer> list = new ArrayList<>();    
        // 先遍历奇数层，然后紧接着判断是否还有偶数层，如果有就接着遍历
        while (size-- > 0) {
            // 奇：从头出，从尾入；先左后右
            root = queue.removeFirst();
            list.add(root.val);
            if (root.left != null) {
                queue.addLast(root.left);
            }
            if (root.right != null) {
                queue.addLast(root.right);
            }
        }
        res.add(list);

        // 处理过奇数层，立刻处理偶数层
        if (!queue.isEmpty()) {
            size = queue.size();
            list = new ArrayList<>();    
            while (size-- > 0) {
                // 偶：从尾出，从头入；先右后左
                root = queue.removeLast();
                list.add(root.val);
                // 每次都是先右后左的顺序入队头，这样就会导致奇数层可以做到从左往右遍历
                if (root.right != null) {
                    queue.addFirst(root.right);
                }
                if (root.left != null) {
                    queue.addFirst(root.left);
                }
            }
            res.add(list);
        }
    }
    return res;

}

// 方法三：双栈
public List<List<Integer>> levelOrderTwoStack(TreeNode root) {
    List<List<Integer>> res = new ArrayList<>();
    Stack<TreeNode> stackOdd = new Stack<>();
    Stack<TreeNode> stackEven = new Stack<>();
    stackOdd.push(root);

    // 两个栈分别存储奇数层和偶数层的元素
    // 如果同时为空，说明遍历完了
    while (!stackOdd.isEmpty() || !stackEven.isEmpty()) {
        List<Integer> list = new ArrayList<>();
        // 刚来到新的一层时只会有一个栈不为空
        if (!stackOdd.isEmpty()) {
            // 如果奇数层栈不为空，则当前是奇数层
            // 奇数层先入左孩子，再入右孩子
            while (!stackOdd.isEmpty()) {
                root = stackOdd.pop();
                list.add(root.val);
                if (root.left != null) {
                    stackEven.push(root.left);
                }
                if (root.right != null) {
                    stackEven.push(root.right);
                }
            }
        } else {
            // 否则当前就是偶数层
            // 偶数层先入右孩子，再入左孩子
            while (!stackEven.isEmpty()) {
                root = stackEven.pop();
                list.add(root.val);
                if (root.right != null) {
                    stackOdd.push(root.right);
                }
                if (root.left != null) {
                    stackOdd.push(root.left);
                }
            }
        }
        res.add(list);
    }
    return res;  
}

二叉树中序遍历的常见题目

模板

许多二叉树问题都可以使用中序遍历 + pre 变量的套路解决。在中序遍历的过程中，使用 pre 变量不断记录当前节点的前一个节点，从而解决问题。其中中序遍历的实现既可以使用递归栈又可以使用 Morris 遍历。

模板一：递归

// pre 变量不断记录当前节点的前一个节点
public Node pre;

public void template01(Node root) {
    if (root == null) {
        return null;
    }
    dfs(root);
}

void dfs(Node cur) {
    if (cur == null) {
        return;
    }
    dfs(cur.left);

    // 如果 pre 已存在（后续的所有节点都符合该情况），则进行业务
    if (pre != null) {
        // 此处进行具体业务：例如比较pre和cur的大小等
    } else {
        // 如果还未设置，此时到达整棵树的最左侧节点（中序遍历的第一个节点），将该节点设置为 pre
        // 记得更新pre
        pre = cur;
    }

    dfs(cur.right);
}

模板二：Morris 遍历

public Node template(Node root) {
    if (root == null) {
        return null;
    }

    Node cur = root;
    Node mostRight = null;
    Node pre = null;
    Node head = null;

    while (cur != null) {
        // 从当前节点的左子树开始找最右节点
        mostRight = cur.left;
        if (mostRight != null) {
            while (mostRight.right != null && mostRight.right != cur) {
                mostRight = mostRight.right;
            }
            if (mostRight.right == null) {
                // 第一次来到mostRight和节点A，建立线索
                mostRight.right = cur;
                // 开始遍历左子树
                cur = cur.left;
                continue;
            }
            if (mostRight.right == cur) {
                // 第二次来到mostRight和节点A
                // 断开线索
                mostRight.right = null;
            }
        }
        // =========================================================
        // 上面都是 Morris 的标准模板，从下面开始才加入 pre 相关的代码
        if (pre != null) {
            // 具体业务
            // 记得更新pre
            pre = cur;
        } else {
            // 更新pre
            pre = cur;
        }
        // =========================================================

        // Morris 遍历标准模板：
        cur = cur.right;
    }
    return head;
}

二叉搜索树与双向链表

剑指 Offer 36. 二叉搜索树与双向链表：输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。

方法一：递归

在

public Node pre, head;

public Node treeToDoublyList01(Node root) {
    if(root == null) return null;
    dfs(root);
    head.left = pre;
    pre.right = head;
    return head;
}

void dfs(Node cur) {
    if(cur == null) return;
    dfs(cur.left);
    if(pre != null) pre.right = cur;
    else head = cur;
    cur.left = pre;
    pre = cur;
    dfs(cur.right);
}

方法二：Morris 遍历

public Node treeToDoublyList02(Node root) {
    if (root == null) {
        return null;
    }

    Node cur = root;
    Node mostRight = null;
    Node pre = null;
    Node head = null;

    while (cur != null) {
        // 从当前节点的左子树开始找最右节点
        mostRight = cur.left;
        if (mostRight != null) {
            while (mostRight.right != null && mostRight.right != cur) {
                mostRight = mostRight.right;
            }
            if (mostRight.right == null) {
                // 第一次来到mostRight和节点A，建立线索
                mostRight.right = cur;
                // 开始遍历左子树
                cur = cur.left;
                continue;
            }
            if (mostRight.right == cur) {
                // 第二次来到mostRight和节点A
                // 断开线索
                mostRight.right = null;
            }
        }
        if (pre != null) {
            // 前后节点建立线索
            pre.right = cur;
            cur.left = pre;
            // 记得更新pre
            pre = cur;
        } else {
            // 更新pre
            pre = cur;
            // 第一次到的节点被标记为head
            head = cur;
        }
        cur = cur.right;
    }
    // 退出循环时，pre指向树的最后一个节点
    pre.right = head;
    head.left = pre;
    return head;
}

方法三：树形 DP

public class ReturnData {
    public Node mostLeft;
    public Node mostRight;
    public ReturnData(Node left, Node right) {
        this.mostLeft = left;
        this.mostRight = right;
    }
}

public Node treeToDoublyList01(Node root) {
    if (root == null) {
        return null;
    }
    // 先找到整棵树的最左侧节点
    globalRoot = root;
    head = root;

    recur(root);
    return head;
}

public Node globalRoot;
public Node head;

public ReturnData recur(Node root) {
    if (root == null) {
        return new ReturnData(null, null);
    }

    ReturnData leftReturn = recur(root.left);
    ReturnData rightReturn = recur(root.right);

    // 获取左子树的最左节点和右子树的最右节点
    Node curMostLeft = leftReturn.mostLeft;
    Node curMostRight = rightReturn.mostRight;

    // 左子树的最右节点要和当前节点建立线索
    if (leftReturn.mostRight != null) {
        leftReturn.mostRight.right = root;
        root.left = leftReturn.mostRight;
    }
    // 右子树的最左节点要和当前节点建立线索
    if (rightReturn.mostLeft != null) {
        rightReturn.mostLeft.left = root;
        root.right = rightReturn.mostLeft;
    }

    // 如果左子树不存在，则当前子树的最左节点就是自身
    if (leftReturn.mostLeft == null) {
        curMostLeft = root;
    }
    // 如果右子树不存在，则当前子树的最右节点就是自身
    if (rightReturn.mostRight == null) {
        curMostRight = root;
    }

    // 如果当前节点等于根节点，则将当前整棵树的最左节点和最右节点串起来
    // 注意这里要用整棵树的最左和最右节点，因为可能左子树的最左节点是空，无法.left
    if (root == globalRoot) {
        head = curMostLeft;
        curMostLeft.left = curMostRight;
        curMostRight.right = curMostLeft;
    }

    // 返回当前子树的最左节点和最右节点
    return new ReturnData(curMostLeft, curMostRight);
}

恢复二叉搜索树

给你二叉搜索树的根节点 root ，该树中的两个节点被错误地交换。请在不改变其结构的情况下，恢复这棵树。示例：

方法一：递归中序遍历

这道题的关键在于正确的分析错误的两个点的位置。例如 [1, 2, 3, 4, 5, 6, 7] 被交换成了 [1, 6, 3, 4, 5, 2, 7]，当中序遍历时，不断判断当前 i 是否大于 i+1

• 如果是，则记录 i 是那个较大的错误点，即 index2，i+1 不是错误点（这点不能乱，错误的是 i，不是i+1）。
• 当再次发现 i > i+1 时，即 5 > 2，此时错误的就不是 i 了，而是 i+1，这个点就是 index1 。
• 最后交换 index1 和 index2

具体实现：只需要在中序遍历的时候不断记录 pred 点（i），比较当前点（i+1）的值。如果pred更大，说明他就是 index2。再找下去，pred 再次大于 cur 时，cur 就是 index1。最后做交换即可

代码：

class Solution {
    public TreeNode errorRoot;
    public TreeNode errorcChild;

    public TreeNode pred; // 当前节点的前辈节点（中序遍历的上一个）
    public TreeNode node01;
    public TreeNode node02;
    public int count = 2;

    public void recoverTree(TreeNode root) {
        // 在递归的时候如果找到了 cur 所在子树不满足
        // 递归时，记录左右子树上的最小值和最大值的节点对象
        // 将 cur 的值与其交换即可
        if (root == null)
            return;
        
        // 官方方法一：中序遍历时记录前一个节点pre，并比较pre和当前节点cur的大小，若发现pre>cur，则记录pre，第二次记录cur
        // 之所以这么定，是因为一个数组里交换两个数字后，第一个错误的数字是大于后面的数字的，第二个则是前一个大于当前的，所以两次取，一次是pre，一次是cur
        inOrderRecur(root);
        
        // 交换错误的两个节点
        int tmp = node01.val;
        node01.val = node02.val;
        node02.val = tmp;
    }

    public void inOrderRecur(TreeNode cur) {
        if (cur == null) {
            return;
        }

        inOrderRecur(cur.left);

        // 要放在中序遍历的位置
        if (pred != null && pred.val > cur.val) {
            // 成立时代表是第二次发现有异常条件，说明该赋值给node02 = cur
            if (--count == 0) {
                // 若能进来，说明两个错误的节点是不相邻的，则更新后者为 cur
                node02 = cur;
            } else {
                // 否则说明是第一次来到当前节点，说明赋值给node01 = pred
                node01 = pred;
                // 并且需要将 cur 赋值给 node02，以免相邻两个数交换时
                // count 只会减一次，永远不会进入上面
                // 这里赋值就能记录到错误交换的两个节点
                node02 = cur;
            }
        }
        // 注意要在第二次回到当前节点时（中序遍历的顺序）将pred更新
        // 接下来遍历其右子树时，pred就更新为了当前节点
        pred = cur;

        inOrderRecur(cur.right);
    }
}

方法二：Morris 中序遍历

对于这种跟中序遍历相关的题目，可以考虑使用 Morris 中序遍历降低空间复杂度。思路同样是在中序遍历的过程中，比较 pred 与 cur 的大小。

代码：

public void recoverTree(TreeNode root) {
    if (root == null) {
        return;
    }
    TreeNode cur = root;
    TreeNode mostRight;
    TreeNode x = null;
    TreeNode y = null;
    TreeNode pred = null;

    while (cur != null) {
        mostRight = cur.left;
        if (mostRight != null) {
            while (mostRight.right != null && mostRight.right != cur) {
                mostRight = mostRight.right;
            }
            if (mostRight.right == null) {
                mostRight.right = cur;
                cur = cur.left;
                continue;
            } else {
                // 中序遍历第二次到达当前节点 A 时回来到这里，并顺利到达下面的 if 外的代码，第一次遍历会被continue给打断
                mostRight.right = null;
            }
        }
        // 这里是 Morris 中序遍历的位置，在这里判断即可
        // 假设正确的顺序是 ... x ... y ...
        // 那么交换后是    ... y ... x ...，
        // y 要设置为 pred，并且只设置一次；x 要设置为 cur，需要设置两次（为了应对xy挨着的情况）
        if (pred != null && pred.val > cur.val) {
            x = cur;
            if (y == null) {
                y = pred;
            }
        }
        // 更新pred和cur
        pred = cur;
        cur = cur.right;
    }
    // 交换 x y
    int tmp = x.val;
    x.val = y.val;
    y.val = tmp;
}

二叉搜索树的第 K 大节点

剑指 Offer 54. 二叉搜索树的第k大节点：给定一棵二叉搜索树，请找出其中第 k 大的节点的值。

思路：

• 维护一个小根堆，只保存 k 个节点的值，中序遍历完毕后堆顶就是第 k 大的节点值
• 倒序中序遍历，k–，效率最高

代码：

// 1. 小根堆
public int kthLargest(TreeNode root, int k) {
    if (root == null || k < 1) {
        return 0;
    }
    // 创建一个小根堆（设置大小为k），中序遍历树，一直将当前元素添加到小根堆里。
    // 遍历完成后，堆顶的就是第k大的
    Queue<Integer> heap = new PriorityQueue<>();
    recur(root, heap, k);
    // heap 堆顶就是答案
    return heap.poll();
}

public void recur(TreeNode root, Queue<Integer> heap, int k) {
    if (root == null) {
        return;
    }
    recur(root.left, heap, k);
    // 不断加到小根堆里
    if (heap.size() < k) {
        heap.offer(root.val);
    } else {
        heap.poll();
        heap.offer(root.val);    
    }
    recur(root.right, heap, k);
}

// 2. 倒序中序遍历
public int kthLargest(TreeNode root, int k) {
    if (root == null) {
        return -1;
    }
    this.K = k;
    recur(root);
    return ans;
}

public int K;
public int ans;
public void recur(TreeNode root) {
    if (root == null) {
        return;
    }

    // 先递归右子树再递归左子树，就能实现倒序的中序遍历
    recur(root.right);
    if (--this.K == 0) {
        // 找到了倒数第k个，记录下
        this.ans = root.val;
        return;
    }
    recur(root.left);
}

树型动态规划问题

模板套路

符合模板套路的特点：可以通过当前节点向左右子树索要一些信息（例如节点数，层数等），从而递归地解决问题。

模板：

public static ReturnData f(Node head) {
    if (head == null) {
        // 根据具体场景返回相应的值
        return ReturnData(xx, xx, xx);
    }
    
    // 先获取左右子树上的返回值
    ReturnData leftReturnData = f(head.left);
    ReturnData rightReturnData = f(head.right);
    
    // 进行判断处理等，例如将 boolean 类型值设置为 true 或 false，设置最大最小值等
    // ...
    
    // 在最后将设置好的值封装成 ReturnData 并向上返回
    return new ReturnData(xx, xx, xx);
}

一些问题需要在当前子树上进行分类：考虑当前节点或不考虑当前节点两种情况，分别计算两种情况中的最优解，进行返回。

叉树节点间的最大距离问题

从二叉树的节点a出发，可以向上或者向下走，但沿途的节点只能经过一次，到达节点b时路径上的节点个数叫作a到b的距离，那么二叉树任何两个节点之间都有距离，求整棵树上的最大距离。

当前子树的最大距离分两种情况：

• 考虑当前节点时：最大距离为左子树的高度 + 右子树高度 + 1
• 不考虑当前节点时：最大距离为左子树上的最大距离或右子树上的最大距离

最后返回二者中的最大值。

代码：

public class MaxDistance {
    public static class TreeNode {
        public int value;
        TreeNode left;
        TreeNode right;

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

    public static class ReturnData {
        // 当前子树的高度
        int height;
        // 当前子树上的最长路径
        int maxLength;
        public ReturnData(int height, int count) {
            this.height = height;
            this.maxLength = count;
        }
    }

    public static int maxDistance(TreeNode root) {
        ReturnData res = process(root);
        return res.maxLength;
    }

    public static ReturnData process(TreeNode root) {
        if (root == null) {
            return new ReturnData(0, 0);
        }

        // 先得到左右子树上的信息
        ReturnData leftReturn = process(root.left);
        ReturnData rightReturn = process(root.right);

        // 先更新当前子树的最大高度
        int curHeight = Math.max(leftReturn.height, rightReturn.height) + 1;

        // 1. 考虑当前节点, 即最长路径包含当前节点
        // 最长路径为: 从左子树上的某个节点一路连接经过当前节点, 到右子树上的另一个节点
        // 最长路径为: 左子树的高度 + 右子树的高度 + 1
        int length1 = leftReturn.height + rightReturn.height + 1;

        // 2. 不考虑当前节点, 即最长路径包含当前节点
        // 最长路径: 左右子树上的最长路径的最大值
        int length2 = Math.max(leftReturn.maxLength, rightReturn.maxLength);

        // 取两种情况的最大值, 返回
        return new ReturnData(curHeight, Math.max(length1, length2));
    }
}

派对的最大快乐值

情况：

• 当前员工要来——其直接下级不能来
• 当前员工不来——其直接下级可以选择：来或不来

代码：

import java.util.List;

public class MaxHappyValue {
    public static class Employee {
        public int happy; // 这名员工可以带来的快乐值
        List<Employee> subordinates; // 这名员工有哪些直接下级
    }

    public static class ReturnData {
        int happyValue;

        public ReturnData(int v) {
            this.happyValue = v;
        }
    }

    public static int maxHappyValue(Employee boss) {
        return Math.max(recur(boss, true), recur(boss, false));
    }

    public static int recur(Employee cur, boolean consider) {
        // 在这里先判断是否有下级, 这样在下面代码里就不需要判断了
        if (cur.subordinates == null) {
            return consider ? cur.happy : 0;
        }
        int p1 = 0;
        int p2 = 0;

        // 两种情况: 1. 考虑当前员工  2. 不考虑当前员工
        // 1. 如果考虑当前员工
        if (consider) {
            p1 += cur.happy;
            // 判断当前员工有无下级:
            // 如果有下级, 遍历所有下级, 同时不能考虑这些下级
            for (Employee subordinate : cur.subordinates) {
                p1 += recur(subordinate, false);
            }
        } else {
            // 2. 如果不考虑当前员工
            // 遍历所有下级, 同时要考虑这些下级
            for (Employee subordinate : cur.subordinates) {
                p2 += recur(subordinate, true);
            }
        }
        return Math.max(p1, p2);
    }

    // 如果存下级, 要用 list 存储, 一对多
    // 如果存上级, 就只用一个常数, 多对一
    // dp[][]的形式：
    public static int maxHappy(int[][] matrix) {
        int[][] dp = new int[matrix.length][2];
        boolean[] visited = new boolean[matrix.length];
        // matrix[0]: 当前员工的上级编号
        // 先找出 root 是谁
        int root = 0;
        for (int i = 0; i < matrix.length; i++) {
            if (i == matrix[i][0]) {
                root = i;
            }
        }
        process(matrix, dp, visited, root);
        return Math.max(dp[root][0], dp[root][1]);
    }

    public static void process(int[][] matrix, int[][] dp, boolean[] visited, int root) {
        // 来到了root, 计算其值后, 就在表中缓存来到过当前位置, 其他分支就不需要再次访问当前位置了
        visited[root] = true;
        // dp[x][0]: 不考虑当前员工
        // dp[x][1]: 考虑当前员工
        // 考虑当前员工root时, 先初始化上matrix中其对应的快乐值
        dp[root][1] = matrix[root][1];

        // 遍历每一个员工, 判断是否为传入的root的下级(如果用树结构, 就是直接获取 list, 不用遍历)
        for (int i = 0; i < matrix.length; i++) {
            // 如果当前员工的上级等于传入的root, 并且当前员工没考虑过(还没遍历到)
            // 就递归当前员工root的下级, 更新root的快乐值
            // 这里的visited就是用来缓存的, 避免重复计算i
            if (matrix[i][0] == root && !visited[i]) {
                // 如果还没计算过i, 就先去计算i的情况, 算完后再回来算i的上级root
                process(matrix, dp, visited, i);
                // 1. 更新 "当前员工i的上级员工root" 考虑自身时的快乐值
                // 考虑root时, 下级i的快乐值就不能算上, 所以要加上下级dp[i][0]: "不考虑自身时的快乐值"
                dp[root][1] += dp[i][0];
                // 2. 更新 root 不考虑自身时的快乐值
                // 不考虑自身, 要取 "考虑下级" 和 "不考虑下级" 中的最大值
                dp[root][0] += Math.max(dp[i][1], dp[i][0]);
            }
        }
    }

    public static void main(String[] args) {
        int[][] matrix = { { 1, 8 }, { 1, 9 }, { 1, 10 } };
        System.out.println(maxHappy(matrix));
    }
}

二叉树的不同种类个数

给定一个非负整数n，代表二叉树的节点个数。返回能形成多少种不同的二叉树结构。

思路：当前位置作为根节点时，左子树的节点个数从 0 开始遍历一直到 n - 1，累加各种情况下当前子树的结构种类：

// 当前子树上有n个节点的前提下：当左子树上有i个节点时, 右子树上有n-1-i个节点(要排除掉root)
res += process(i, record) * process(n - 1 - i, record);

代码：

public class NumberOfTree {

    public static int numberOfTree(int n) {
        int[] record = new int[n + 1];
        return process(n, record);
    }

    private static int process(int n, int[] record) {
        // n: 当前子树上拥有的节点个数
        if (n < 0) {
            return 0;
        }
        // root = null
        if (n == 0) {
            return 1;
        }
        // null <- root -> null
        if (n == 1) {
            return 1;
        }
        // left <- root -> null 或 null <- root -> right
        if (n == 2) {
            return 2;
        }
        // 缓存表, 避免重复计算
        if (record[n] != 0) {
            return record[n];
        }

        int res = 1;
        // 遍历决定当前节点的左子树上有多少个节点, 范围: 从0到n-1
        for (int i = 0; i <= n - 1; i++) {
            // 当左子树上有i个节点时, 右子树上有n-1-i个节点(要排除掉root)
            res += process(i, record) * process(n - 1 - i, record);
        }
        return res;
    }

    public static void main(String[] args) {
        System.out.println(numberOfTree(4));
    }
}