0. 框架模型

基本的框架已经在基础知识介绍过了，比如前中后序的递归，非递归遍历，层次遍历等。

a. 向左右子树要信息的框架

我们的这款框架中要列出所有的可能性，比如说和根节点有关和跟节点无关两种。下面介绍解题思路步骤，

首先根据二叉树递归解法的前提，假定可以向左右子树要的信息
考虑得到答案的可能性？列出可能性，和根节点有关么？
根据可能性，确定左右子树分别需要什么信息
信息汇总，求全集定信息体
写递归

写递归时的步骤如下，

定义好Info结构体
递归函数process的返回Info
base case也就是空树返回
从左右子树要信息
根据列出的可能性，把Info中所有的信息加工出来，如果base case处理返回是null节点，这时候就要注意判空！

b. 一次性遍历一层的层次遍历

在一些问题中我们希望，如果能一次性的把一层的节点遍历完，把这一层节点暂存在队列中再作处理。

private void widthOfBinaryTree(TreeNode root) {
    // 层次遍历中的，一次能遍历一层的框架
    if (root == null){
        return;
    }
    // 选用双端队列实现队列，可以做到对队首和队尾元素的选取
    Deque<TreeNode> queue = new LinkedList<NodeWithIndex>();
    queue.offer(root);
    int size = 0;
    while (!queue.isEmpty()){
        // 统计这一层节点的数目
        size = queue.size();
          // 一次性的遍历完
        for (int i = 0; i < size; i++){
            cur = queue.poll();
            if (cur.left!=null){
                queue.offer(cur.left);
            }
            if (cur.right!=null){
                queue.offer(cur.right);
            }
        }
          // 做处理
          dosomething;
    }
}

c. BST的框架

查找框架不涉及到修改二叉树，返回值为void

void BST(TreeNode root, int target) {
    if (root.val == target)
        // 找到目标，做点什么
    // 类比于有序数组的二分查找，root.val就是arr[mid]
    if (root.val < target) 
        BST(root.right, target);
    if (root.val > target)
        BST(root.left, target);
}

插入和删除涉及到修改二叉树，返回值为TreeNiode，一般返回修改后的root node

TreeNode insertIntoBST(TreeNode root, int val) {
    // 找到空位置插入新节点
    if (root == null) return new TreeNode(val);
    if (root.val < val) 
        root.right = insertIntoBST(root.right, val);
    if (root.val > val) 
        root.left = insertIntoBST(root.left, val);
    return root;
}

TreeNode deleteNode(TreeNode root, int key) {
    if (root == null){
          // 如果没有找到要删除的节点
        return;
    }
    if (root.val == key) {
        // 找到啦，进行删除
    } else if (root.val > key) {
        // 去左子树找
        root.left = deleteNode(root.left, key);
    } else if (root.val < key) {
        // 去右子树找
        root.right = deleteNode(root.right, key);
    }
    return root;
}

1. 递归框架

1.1 采用基本框架

二叉树镜像

ZJ-27 : 请完成一个函数，输入一个二叉树，该函数输出它的镜像。

解题思路:
递归和遍历都是一样的思路，遍历每个点，交换它的左右子树。
时间复杂度:O(N)；空间复杂度:O(N)

方法一: 递归方法

public TreeNode mirrorTree(TreeNode root) {
    if(root == null){
        return root;
    }
    process(root);
    return root;
}

public static void process(TreeNode node){
    if(node == null){
        return;
    }

    // 方法一: 先序遍历
    // 根据递归序，第一次来到这个节点，交换左右子树
    TreeNode temp = node.left;
    node.left = node.right;
    node.right = temp;

    process(node.left);
    process(node.right);

    // 方法二: 中序遍历
    // 递归序，第二次来到这个节点，注意是遍历两次left节点，因为交换过了
    process(node.left);

    TreeNode temp = node.left;
    node.left = node.right;
    node.right = temp;

    process(node.left);

    // 方法三: 后序遍历
    process(node.left);
    process(node.right);

    TreeNode temp = node.left;
    node.left = node.right;
    node.right = temp;

}

方法二: 非递归, 和递归思路一样，人工压栈，但还是每个节点交换左右子数

// 层次遍历
public TreeNode mirrorTree(TreeNode root) {
    if(root == null){
        return root;
    }
    // 层次遍历的方法
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    // 遍历队列
    while(!queue.isEmpty()){
        TreeNode cur = queue.poll();


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

        // 交换左右子树
        TreeNode temp = cur.left;
        cur.left = cur.right;
        cur.right = temp;
    }
    return root;
}

// 非递归中序遍历
public TreeNode mirrorTree(TreeNode root) {
    if(root == null){
        return root;
    }
    // 非递归的中序遍历
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode cur = root;
    while(cur!=null || !stack.isEmpty()){
        if(cur!=null){
            stack.push(cur);
            cur = cur.left;
        }else{
            TreeNode curTemp = stack.pop();
            // 先记录原本的右子树
            cur = curTemp.right;
            // 交换左右子树
            TreeNode temp = curTemp.left;
            curTemp.left = curTemp.right;
            curTemp.right = temp;

            // ***** 也可以这样 *****
            cur = stack.pop();
            // 交换左右子树
            TreeNode temp = cur.left;
            cur.left = cur.right;
            cur.right = temp;
            // 再次左分解，左子树，其实是右子树
            cur = cur.left;
        }
    }
    return root;
}

1.2 单独考虑根节点

直径的二叉树

LC543. 二叉树的直径

给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。

示例 :
给定二叉树

返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。

注意：两结点之间的路径长度是以它们之间边的数目表示。

解题思路：

注意题目中的提示，这个最大路径可能穿过也可能不穿过根节点，也就是说得到答案可能性有多种，路径的最大值可能不需要经过根节点计算，所以我们需要一个全局变量记录最大值。

图片说明

如上图所示，和根节点无关，答案是来自右子树的最大距离。假设我们知道对于该节点的左儿子向下遍历经过最多的节点数 L（即以左儿子为根的子树的深度）和其右儿子向下遍历经过最多的节点数 R （即以右儿子为根的子树的深度），那么以该节点为起点的路径经过节点数的最大值即为 L+R+1 。我们得到经过该节点的最多路径节点数是dNode，那么其直径就是dNode - 1，因为路径长度是以它们之间边的数目表示，边和点的数目正好差一。

我们想要找到最大直接，就要找到整颗树上对每个点计算其经过的最大经过的节点数，用一个全局变量去找到最大值，这里值得注意的就是，根节点并不代表着最大值。

最后的算法流程为：

我们定义一个递归函数 depth(node) 计算最大经过的节点数，函数返回该节点为根的深度。先递归调用左儿子和右儿子求得它们为根的树的深度 L 和 R ，则该节点为根的子树的深度即为max(L,R)+1，该节点的最大经过的节点数为L+R+1。

递归搜索每个节点并设一个全局变量ans，记录并比较每个节点的最大经过节点数，最后找到最大的减一返回。

class Solution {
    // 假设初始化一个节点，不要随意使用static变量
    int ans;
    public int diameterOfBinaryTree(TreeNode root) {
        ans = 1;
        if (root == null){
            return 0;
        }
        process(root);
        // 最长路径就是最大节点数-1
        return ans - 1;
    }

    private int process(TreeNode root){
        // base case: 空节点返回0
        if (root == null){
            return 0;
        }
        // 深度代表了最大经历的节点数目
        int leftInfo = process(root.left);
        int rightInfo = process(root.right);

        // 根节点的信息是，左数目+右数目+1
        // 最大节点数就是左节点数+右节点数+自己(1)
        // 再比较每个节点的信息，找到最大值
        ans = Math.max(ans, leftInfo+rightInfo+1);

        // 求根节点的深度, 左右深度最大值 + 1
        return Math.max(leftInfo, rightInfo) + 1;
    }
}

1.3 复杂度优化

完全二叉树的节点个数

力扣222，给出一个完全二叉树，求出该树的节点个数。

说明：

完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。

示例:输入:
1
/
2 3
/ \ /
4 5 6

输出: 6

解题思路：

这道题要结合完全二叉树的性质来做，时间复杂度要小于O(N)。完全二叉树(Complete Binary Tree)的定义可以理解为，它是一颗满二叉树或者正在依次逐层成为满二叉树，这里的依次是指从左子树到右子树。它的性质就是，一颗完全二叉树的左右子树，至少有一颗是满二叉树，下图参考labuladong公众号

图片说明

public static int countNodes(TreeNode root) {
    TreeNode leftNode = root;
    TreeNode rightNode = root;
    int leftHeight = 0;
    int rightHeight = 0;
    // 统计左子树的高度
    while (leftNode != null){
        leftNode = leftNode.left;
        leftHeight++;
    }
    // 统计右子树的高度
    while (rightNode != null){
        rightNode = rightNode.right;
        rightHeight++;
    }
    // 如果是左右等高，则是满二叉树
    if (rightHeight == leftHeight){
        return (int)Math.pow(2, rightHeight)-1;
    }
    // 如果不等高，根左右累加起来
    // 复杂度计算，只会有一个递归到底，所以复杂度是log(N)
    // 每次递归时，计算复杂度是log(N)
    // 所以最后的复杂度是，(h)ˆ2，h=log(N)
    return 1 + countNodes(root.left) + countNodes(root.right);
}

分析上述代码的时间复杂度，最后一行的左右子树递归中，只会有一个递归到底，另一个会因为是满树而提前返回。比如说root.left是满树，关于它的递归函数，只会一次执行中间的判断树的高度的代码，从而证明他是满树直接通过公式计算返回节点数目，其复杂度是O(log(N))。

root.right不是满树的话，最多会递归h层，h就是树的高度，每层会执行log(N)的操作，因此复杂是O(log(h)ˆ2)，是远远低于O(N)的复杂度。所以说，完全二叉树这个概念还是有它存在的原因的，不仅适用于数组实现二叉堆，而且连计算节点总数这种看起来简单的操作都有高效的算法实现。

备注:

// 普通二叉树计算节点个数，复杂度是O(N)
public int countNodes(TreeNode root) {
    if (root == null) return 0;
    return 1 + countNodes(root.left) + countNodes(root.right);
}

// 如果是一棵满二叉树，节点总数就和树的高度呈指数关系，时间复杂度 O(logN)
public int countNodes(TreeNode root) {
    int h = 0;
    // 计算树的高度
    while (root != null) {
        root = root.left;
        h++;
    }
    // 节点总数就是 2^h - 1
    return (int)Math.pow(2, h) - 1;
}

1.4 层次遍历是更好解法

BT的最大宽度

LC662-二叉树最大宽度

给定一个二叉树，编写一个函数来获取这个树的最大宽度。树的宽度是所有层中的最大宽度。这个二叉树与满二叉树（full binary tree）结构相同，但一些节点为空。

每一层的宽度被定义为两个端点（该层最左和最右的非空节点，两端点间的null节点也计入长度）之间的长度。

示例 1:

输入:

       1
     /   \
    3     2
   / \     \  
  5   3     9

输出: 4
解释: 最大值出现在树的第 3 层，宽度为 4 (5,3,null,9)。

解题思路：

设想给每个节点编号，其子节点的编号就是left = 2*index, right = 2*index+1，再利用一次性宽度的层次遍历框架，计算这一层的第一个节点和最后一个节点的差值就是这层的宽度，最后再找到所有层中的最大宽度即可。

private static int widthOfBinaryTree(TreeNode root) {
    // 层次遍历中的，一次能遍历一层的框架
    if (root == null){
        return 0;
    }
    // 选用双端队列实现队列，可以做到对队首和队尾元素的选取
    Deque<NodeWithIndex> queue = new LinkedList<NodeWithIndex>();
    queue.offer(new NodeWithIndex(root, 1));
    NodeWithIndex cur = null;
    int index = 0;
    int size = 0;
    int width = 0;
    while (!queue.isEmpty()){
          // 最大宽度就是，找到每层中最后节点减去首节点再加一的最大值
        width = Math.max(width, queue.peekLast().index - queue.peekFirst().index + 1);
        size = queue.size();
        for (int i = 0; i < size; i++){
            cur = queue.poll();
            root = cur.node;
            index = cur.index;

            if (root.left!=null){
                queue.offer(new NodeWithIndex(root.left, 2*index));
            }
            if (root.right!=null){
                queue.offer(new NodeWithIndex(root.right, 2*index + 1));
            }
        }
        //width = Math.max(width, queue.peekLast().index - queue.peekFirst().index + 1);
    }
    return width;
}

// 对现有节点改造下，加入一个index的新属性
private static class NodeWithIndex{
    TreeNode node;
    int index;
    public NodeWithIndex(TreeNode node, int index) {
        this.node = node;
        this.index = index;
    }
}

此外也可以用深度优先遍历解决，也需要给每个节点编号，并需要一个depth来记录当前节点的深度，并巧妙的利用一个map来记录，当每层的第一次加入节点的编号，因为是先序框架，所以第一个节点一定是最左边的节点，在后序的递归过程中，可以查询表，让当前层的所有节点依次去计算和这个最左节点的距离，找到最大值就是最大宽度。

// 查询表
static HashMap<Integer, Integer> map;
static int ans;
private static int widthOfBinaryTreeRecursive(TreeNode root) {
    if (root == null){
        return 0;
    }
    map = new HashMap<Integer, Integer>();
    // 根节点
    map.put(0, 0);
    ans = 0;
    dfs(root, 0, 0);
    return ans;
}

private static void dfs(TreeNode root, int depth, int pos){
    if (root == null){
        return;
    }
    // 如果depth不存在，就按照方程加入pos，保证加入的都是每一层的最左pos
    map.computeIfAbsent(depth, x->pos);
      //     最奇妙的地方，每次查询depth得到当前层的最左节点！
    int left = map.get(depth);
    ans = Math.max(ans, pos - left + 1);
    dfs(root.left, depth+1, 2*pos);
    dfs(root.right, depth+1, 2*pos+1);
}

2. 序列化框架

参考资料，东哥公共号lobuladong

序列化和反序列化的目的，以某种固定格式组织字符串，使得数据可以独立于编程语言。那么假设现在有一棵用 Java 实现的二叉树，我想把它序列化字符串，然后用 C++ 读取这棵并还原这棵二叉树的结构，怎么办？这就需要对二叉树进行序列化和反序列化了。

可以解决题目LC297，给你输入一棵二叉树的根节点 root，要求你实现如下一个类：

public class Codec {

    // 把一棵二叉树序列化成字符串
    public String serialize(TreeNode root) {}

    // 把字符串反序列化成二叉树
    public TreeNode deserialize(String data) {}
}

我们可以用 serialize 方法将二叉树序列化成字符串，用 deserialize 方法将序列化的字符串反序列化成二叉树，至于以什么格式序列化和反序列化，这个完全由你决定。

serialize 方法也许会把它序列化成字符串 2,1,#,6,3,#,#，其中 # 表示 null 指针，,表示分隔符，代表一个值的结束，必须有分隔符，它可以唯一的区分一棵二叉树，否则在序列中123，根节点是12还是23呢？把这个字符串再输入 deserialize 方法，依然可以还原出这棵二叉树。也就是说，这两个方***成对儿使用，你只要保证他俩能够自洽就行了。

PS：一般语境下，单单前序遍历结果是不能还原二叉树结构的，因为缺少空指针的信息，至少要得到前、中、后序遍历中的两种才能还原二叉树。但是这里的 node 列表包含空指针的信息，所以只使用 node 列表就可以还原二叉树。

2.1 前中后序遍历

前序方法：

序列化的方法很简单，就是在前序遍历的框架上加上添加字符的部分，注意在base case时当节点为空，添加 # 。采用StringBuilder()可以更高效稳定的拼接字符串。

// 把一棵二叉树序列化成字符串
private static String serialize(TreeNode root) {
    StringBuilder sb = new StringBuilder();
    preTraversal(root, sb);
    return sb.toString();
}

// 序列化是需要递归的，需要一个辅助函数
private static void preTraversal(TreeNode root, StringBuilder sb){
    // base case:
    if (root == null){
        sb.append("#").append(",");
        return;
    }
    // 加入字符，用分隔符分开
    // 前序遍历框架
    sb.append(root.val).append(",");
    preTraversal(root.left, sb);
    preTraversal(root.right, sb);
}

反序列化的方法，参考接收到的序列化后的结果，首先根据分隔符就可以得到节点列表，观察就可以发现第一个节点就是根节点，这样我们就可以借助一个队列采用递归的方式恢复出这个二叉树。下图作者是dong哥，其图片来自其公众号，水印是labuladong。

图片说明

先确定根节点 root，然后遵循前序遍历的规则，递归生成左右子树。这里巧妙的是，因为序列化的时候记录了空节点，所以当递归恢复叶子节点时，递归函数会在执行到叶子节点的左右子树时，返回空，这样叶子节点就只会返回它本身。序列化时是采用前序遍历，反序列化时也采用根，左孩子，右孩子的顺序递归恢复，只需要额外的把队列中的元素从头到尾依次弹出。

// 把字符串反序列化成二叉树
private static TreeNode deserialize(String data) {
    // 把接收到的字符串，先分割再依次装入到队列中
    Queue<String> str = new LinkedList<String>();
    for(String string : data.split(",")){
        str.offer(string);
    }
    return deserialize_process(str);
}

// 反序列化是需要递归的，需要一个辅助函数
private static TreeNode deserialize_process(Queue<String> str){
    // 力扣做题防止空输入
    if (str.isEmpty()){
        return null;
    }
    String cur = str.poll();
    // base case:
    if (cur.equals("#")){
        return null;
    }

    TreeNode root = new TreeNode(Integer.parseInt(cur));
    root.left = deserialize_process(str);
    root.right = deserialize_process(str);
    return root;
}

后序方法：

序列化的方法和前序的一致，注意添加字符的顺序放在遍历之后，根据递归序，根节点会最后加入序列。

// Encodes a tree to a single string.
private static String serialize(TreeNode root) {
    StringBuilder sb = new StringBuilder();
    serialize_process(root, sb);
    return sb.toString();
}

// 后序遍历的序列化辅助递归函数
private static void serialize_process(TreeNode root, StringBuilder sb){
    // base case:
    if (root == null){
        sb.append("#").append(",");
        return;
    }
    serialize_process(root.left, sb);
    serialize_process(root.right, sb);
    // 后序遍历
    sb.append(root.val).append(",");
}

反序列化的方法，要根据序列化的顺序做出改变，因为根节点在序列的最后，我们应该从后往前取出列表元素，先用最后一个元素构造 root，然后递归调用生成 root 的左右子树。注意，根据上图，从后往前在 nodes 列表中取元素，一定要先构造 root.right 子树，后构造 root.left 子树。

图片说明

我们在从序列化的结果恢复成节点列表时，采用栈这个容器，就可以保证本来在末尾的根节点可以第一个被处理，从而完成从后往前的从列表中取元素。

// Decodes your encoded data to tree.
// 反序列化
private static TreeNode deserialize(String data) {
    // 先把字符串分割提取，针对后序遍历要用栈，因为根节点是最后加入的
    Deque<String> stack = new ArrayDeque<String>();
    for (String str : data.split(",")){
        stack.push(str);
    }
    return deserialize_process(stack);
}

// 后序遍历反序列化需要借助递归辅助函数
private static TreeNode deserialize_process(Deque<String> stack){
    if (stack.isEmpty()){
        return null;
    }
    String cur = stack.pop();
    if (cur.equals("#")){
        return null;
    }
    TreeNode root = new TreeNode(Integer.parseInt(cur));
    // 因为后序遍历的顺序，所以递归先建立出的是右子树，再是左子树
    root.right = deserialize_process(stack);
    root.left = deserialize_process(stack);
    return root;
}

中序方法：

中序方法无法做到反序列化，原因是，不同于前序和后序遍历，中序遍历的根节点在中间无法定位到他的具***置。

至此可以小结下，这种生成一个二叉树的模版就是，先要生成根节点，再递归的产生左右子树。

// base case，基于某个条件返回null
if (cur.equals("#")){
  return null;
}
TreeNode root = new TreeNode(Integer.parseInt(cur));
// 递归建立出右子树，左子树
root.right = deserialize_process(stack);
root.left = deserialize_process(stack);
return root;

2.2 层次遍历

序列化的方法，和前后序遍历很相似，就是在遍历节点的过程中加入转换字符的功能，在标准的二叉树层级遍历框架中，从上到下，从左到右打印每一层二叉树节点的值，可以看到，队列 q 中不会存在null指针。不过我们在反序列化的过程中是需要记录空指针null的，所以可以把标准的层级遍历框架略作修改：

// 把一棵树序列化，再逆序列化，采用层次遍历模式
// 借助层次遍历的框架，需要一个队列
private static String serialize(TreeNode root) {
    // 如果是空树，直接返回
    if (root == null){
        return new String("#,");
    }

    StringBuilder sb = new StringBuilder();
    Queue<TreeNode> queue = new LinkedList<TreeNode>();
    queue.offer(root);
    // 注意根节点要单独的在这里要添加字符！
    sb.append(root.val).append(",");
    TreeNode cur = null;

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

        if (cur.left!=null){
            sb.append(cur.left.val).append(",");
            queue.offer(cur.left);
        }else {
            sb.append("#,");
        }

        if (cur.right!=null){
            sb.append(cur.right.val).append(",");
            queue.offer(cur.right);
        }else{
            sb.append("#,");
        }
    }
    return sb.toString();
}

反序列化方法，类比前后遍历递归的恢复树，层次遍历方法没有递归时的系统栈，因此需要自己额外建立一个队列帮助自己。

图片说明

可以看到，每一个非空节点都会对应两个子节点，那么反序列化的思路也是用队列进行层级遍历，同时用索引 i 记录对应子节点的位置，序列化时操作二叉树节点 TreeNode，反序列化时我们的函数在操作 nodes[i]。

// 反序列化
// 序列化是在二叉树上层次遍历，反序列化是在数组上利用下标i遍历左右节点
// 反序列化要借助辅助队列
private static TreeNode deserialize(String data) {
    // 根据分隔符获得节点数组
    String[] nodes = data.split(",");
    int i = 0;

    // 第一个元素就是根节点
    TreeNode root = generateNodeByStr(nodes[i++]);
    Queue<TreeNode> queue = new LinkedList<TreeNode>();
    TreeNode cur = null;
    // 头节点不是空是，才加入队列
    if (root!=null){
        queue.offer(root);
    }

    while(!queue.isEmpty()){
        cur = queue.poll();
        // 生产左右子树
        TreeNode left = generateNodeByStr(nodes[i++]);
        TreeNode right = generateNodeByStr(nodes[i++]);
        cur.left = left;
        cur.right = right;
        // 检查左右子树
        if (left!=null){
            queue.offer(left);
        }
        if (right!=null){
            queue.offer(right);
        }
    }
    return root;
}

private static TreeNode generateNodeByStr(String str){
    if (str.equals("#")){
        return null;
    }else {
        return new TreeNode(Integer.parseInt(str));
    }
}

2.3 应用

寻找重复的子树

LC652. 寻找重复的子树

给定一棵二叉树，返回所有重复的子树。对于同一类的重复子树，你只需要返回其中任意一棵的根结点即可。两棵树重复是指它们具有相同的结构以及相同的结点值。

以下图的树为例，应该返回节点4和2，分别代表子树[4]和[2,4]。

图片说明

解题思路，二叉树的老套路，先思考，对于某一个节点，它应该做什么。如果你想知道以自己为根的子树是不是重复的，是否应该被加入结果列表中，你需要知道什么信息？

你需要知道以下两点：

1、以我为根的这棵二叉树（子树）长啥样？

2、以其他节点为根的子树都长啥样？

针对第一个问题，可以采用之前学习到的序列化的知识，可以把这颗二叉树唯一的序列化表示。可以采用后序框架，此时可以完整的描述以“我”为根的这个树的序列化，至于按什么顺序拼接序列化的字符串，这个随意。

针对第二个问题，可以借助外部查询表，因为是找到重复的子树，所以表中重复的元素就是想要的答案，此外还要注意，题目要求只把重复的节点加入一次，所以只需要一个小技巧，就是当加入第二次时，才把元素加入答案容器中。

static HashMap<String, Integer> memo;
static List<TreeNode> list;
private static List<TreeNode> findDuplicateSubtrees(TreeNode root) {
    // 建立外部变量
    memo = new HashMap<String, Integer>();
    list = new ArrayList();
    traversal(root);
    return list;
}

private static String traversal(TreeNode root){
    // base case:
    if (root == null){
        return "#";
    }
    // 选择后序遍历
    String res = root.val + "," + traversal(root.left) + "," + traversal(root.right);

    if (!memo.containsKey(res)){
        memo.put(res, 1);
    }else {
        int times = memo.get(res);
        // 说明已经一次记录，这次就会重复第一次
        if (times == 1){
            list.add(root);
        }
        memo.put(res, times+1);
    }

    // 可以简化查询代码，getOrDefault方法就是没有查询到key的记录时，返回用户设置的defaultValue
    memo.put(res, memo.getOrDefault(res, 0) + 1);
    if (memo.get(res) == 2)
        list.add(root);
    return res;
}

3. 重建二叉树

4. 二叉搜索树

二叉搜索树(BST)的定义：

1、对于 BST 的每一个节点node，左子树节点的值都比node的值要小，右子树节点的值都比node的值大。

2、对于 BST 的每一个节点node，它的左侧子树和右侧子树都是 BST。

此外还有一个重要的性质：BST 的中序遍历结果是有序的（升序）。

4.1 增删改查

BST的第K大节点

力扣题号: 54 - 给定一棵二叉搜索树，请找出其中第k大的节点。

解题思路:
正常的中序遍历是，左中右，遍历下来的数组是从小到大，而题目要求是第K大，我们可以自己加工一个中序遍历是，右中左，这样数组是从大到小，遍历到第K个就是想要的答案。

public int kthLargest(TreeNode root, int k) {
    // 自己构造一种遍历方法，右-中-左
    // 用非递归的方法中序遍历二叉树
    TreeNode cur = root;
    int index = 1;
    int KthValue = -1;
    Deque<TreeNode> stack = new ArrayDeque<>();
    while(cur!=null || !stack.isEmpty()){
        // 不停地压入右孩子
        if(cur!=null){
        stack.push(cur);
        cur = cur.right;
        }else{
        // 弹出栈顶
        cur = stack.pop();
        if(index == k){
            KthValue = cur.val;
        }
        index++;
        cur = cur.left;
        }
    }
    return KthValue;
}

在java官网中，推荐我们不要使用Stack类，而是使用Deque类

Deque<TreeNode> stack = new ArrayDeque<>();
// 压入
stack.push(cur);
// 弹出
cur = stack.pop();
// 栈顶元素
cur = stack.peek();

当然也可以采用中序遍历的递归框架：

int res = 0;
int rank = 0;
public int kthLargest(TreeNode root, int k) {
    inOrderTraverse(root, k);
    return res;
}
public void inOrderTraverse(TreeNode root, int k){
    if(root == null){
        return;
    }
    // 稍微改造下，先遍历右边
    inOrderTraverse(root.right, k);
    rank++;
    if(rank == k){
        res = root.val;
        return;
    }
    inOrderTraverse(root.left, k);
}

BST的第K小节点

力扣230. 二叉搜索树中第K小的元素

给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。

说明：
你可以假设 k 总是有效的，1 ≤ k ≤ 二叉搜索树元素个数。

解题思路：

利用 BST 的中序遍历其实就是升序排序，找到第 K 个元素，可以采用递归和非递归框架。

int res = 0;
int nodeInd = 0;
public int kthSmallest(TreeNode root, int k) {
    process(root, k);
    return res;
}

// 返回值类型是void，突发性的返回一个值
private void process(TreeNode root, int k){
    if (root == null){
        return;
    }
    process(root.left, k);
    // 递归序中，第二次来到自己时才更新序号
    nodeInd++;
    if (nodeInd == k){
        res = root.val;
        return;
    }
    process(root.right, k);
}

进阶思路：

参考大道至简

如果我们可以改造节点，让每个节点知道自己的排名，就可以采用二分的方法去查找。如何知道自己的排名呢，需要统计每个节点，以自己为根的二叉树有多少个节点，对于每个节点node就可以通过node.left推导出node的排名。node的排名等于getSize(node.left)+1。

// 第三种进阶方法，知道每个节点的size，就是以这个节点为根的子树的节点个数
// 前提：一定会有这个节点的
public int kthSmallest(TreeNode root, int k) {
    int num = getNodeNum(root.left);
    while (true){
        if (num+1 == k){
            return root.val;
        }else if (num+1 > k){
              // root.left的排名大于k，则在left子树中寻找
            root = root.left;
            num = getNodeNum(root.left);
        }else { // num+1 < k
              // root.left的排名小于k，则在right子树中寻找
            root = root.right;
              // k要更新为 在右子树中的相对kth，因为k已经比整个左子树的节点数大
            k = k - (num+1);
            num = getNodeNum(root.left);
        }
    }
}
// 以当前节点为根的子树的节点总数
public int getNodeNum(TreeNode node){
    if (node == null){
        return 0;
    }
    return 1 + getNodeNum(node.left) + getNodeNum(node.right);
}

BST的搜索

力扣700. 二叉搜索树中的搜索

给定二叉搜索树（BST）的根节点和一个值。你需要在BST中找到节点值等于给定值的节点。返回以该节点为根的子树。如果节点不存在，则返回 NULL。

解题思路：

public TreeNode searchBST(TreeNode root, int val) {
    if(root == null){
        return null;
    }
    if(val == root.val){
        return root;
    }else if(root.val > val){ // 中间值大于目标值，在左半部分寻找
        return searchBST(root.left, val);
    }else{
        return searchBST(root.right, val);
    }
}

// 迭代框架
public TreeNode searchBST(TreeNode root, int val) {
    // 迭代模版的
    while(root!=null && root.val!=val){
        root = root.val > val ? root.left : root.right;
    }
    return root;
}

BST的插入

力扣701. 二叉搜索树中的插入操作

给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。返回插入后二叉搜索树的根节点。输入数据保证，新值和原始二叉搜索树中的任意节点值都不同。

解题思路：

public TreeNode insertIntoBST(TreeNode root, int val) {
    // 找到空位置，插入
    if(root == null){
        return new TreeNode(val);
    }
    if(root.val > val){
        root.left = insertIntoBST(root.left, val);
    }else{
        root.right = insertIntoBST(root.right, val);
    }
    return root;
}

BST的删除

给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。

一般来说，删除节点可分为两个步骤：

首先找到需要删除的节点；
如果找到了，删除它。
说明：要求算法时间复杂度为 O(h)，h 为树的高度。

解题思路：

先采用查找的框架，去寻找这个节点，如果它不存在就不作修改，返回原来的根节点。如果找到了要删除的节点，则需要分情况讨论：

情况一：node恰好是末端节点，两个子节点都为空，可以直接删除，图片来自力扣，下同

图片说明

情况二：node只有一个孩子，则直接让它的孩子接替它的位置

图片说明

情况三：node有两个孩子，必须找到左子树中最大的那个节点，或者右子树中最小的那个节点来接替自己

图片说明

// 返回二叉搜索树（有可能被更新）的根节点的引用。
private TreeNode deleteNode(TreeNode root, int key) {
    // 框架是，查找加上修改
    if (root == null){
        return null;
    }
    if (key > root.val){
        root.right = deleteNode(root.right, key);
    }else if (key < root.val){
        root.left = deleteNode(root.left, key);
    }else {
        // 找到了待删除的节点了，分情况讨论
        // 情况1：叶子结点 和 情况二：单孩子节点
        if (root.left == null){
            return root.right;
        }
        if (root.right == null){
            return root.left;
        }
        // 情况三：左右孩子都不为空
        // 1. 记录待删除的节点
        TreeNode t = root;
        // 2. 找到左子树中的最小节点，接替它
        root = getMin(t.right);
          // 3. 左子树中的最小节点，它的左孩子一定为空，但还要处理它可能不为空的右孩子
        root.right = deleteMin(t.right);
        root.left = t.left;
    }
    // 返回递归修改后的根
    return root;
}

// 找到并返回，二叉树以node为根的最小节点，也就是最左节点
private TreeNode getMin(TreeNode node){
    if (node == null){
        return null;
    }
    while (node.left != null){
        node = node.left;
    }
    return node;
}

// 以node为根，找到树上的最小节点，并把它的右孩子接替它的位置，并返回根节点(可能更新了)
private TreeNode deleteMin(TreeNode node){
      // 如果node的left为空，就
    if (node.left == null){
        return node.right;
    }
      // 跨越两层节点
    node.left = deleteMin(node.left);
    return  node;

      // 非递归的容易理解
    // 记录原始节点
      TreeNode root = node;
       // 如果第一个节点就是最右节点，直接返回它的右孩子
    if (node.left == null){
        return node.right;
    }
    // 递推更新，保留到祖父节点
    while(node.left.left!=null){
        node = node.left;
    }
    // 看图说话
    node.left = node.left.right;
    return root;
}

图片说明

4.2 利用BST的性质

验证BST

力扣98. 验证二叉搜索树

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

解题思路：

利用BST中序遍历是生序的性质，依次判断遍历的数，如果不符合立刻返回false

long pre = Long.MIN_VALUE;
boolean res = true;
public boolean isValidBST(TreeNode root) {
    if(root == null){
        return true;
    }
    process(root);
    return res;
}

public void process(TreeNode root){
    if(root == null){
        return;
    }
    process(root.left);
    // 比较当前遍历值 和 之前的值
    if(pre >= root.val){
        res = false;
    }
    // 更新当前值
    pre = root.val;
    process(root.right);
}

非递归框架：

public boolean isValidBST(TreeNode root) {
    if (root==null){
        return true;
    }
    Stack<TreeNode> stack = new Stack<>();
    TreeNode node = root;
    double pre = - Double.MAX_VALUE;
    while(!stack.isEmpty() || node!=null){
        // 左遍历
        if(node!=null){
            stack.push(node);
            node = node.left;
        }
        // 退出左遍历，先弹出一个节点，在对右节点执行左遍历
        else{
            node = stack.pop();
            if(node.val <= pre){
                return false;
            }
            pre = node.val;
            node = node.right;
        }
    }
    return true;
}

最低公共祖先

力扣236：给定一个二叉树, 找到该树中两个指定节点p和q(一定在树上)的最近公共祖先。

解题思路：

1.递归方法

参考力扣题解Krahets , Anish.Hui 和 labuladong

递归套路思考：

本身函数需要返回什么？最低公共父节点
整合左右子树返回的信息？以子树为头节点的整棵树的最低公共父节点
整合规则？

递归解析：

终止条件(base case):
- 当到达叶子结点的子树时，返回Null
- 当root=q / p时，返回根节点本身
递推工作：
- 开启递归左子节点，返回值记为 left
- 开启递归右子节点，返回值记为 right
整合规则：
- 当左右子树的返回都是空，说明查询节点都不在左右子树上，则返回空
- 当左右子树都不是空，说明p和q恰好分布在左右子树上，此时root就是他们的最低公共祖先，并返回
- 当左子树不为空，右子树为空，则返回左子树，说明p和q都分布在左子树上，p和q可能均匀的分布在左子树为根的树的两侧，也可能其中一个就是左子树
- 同理，右子树不为空时，返回右子树

对于整合情况二中，left和right非空，分别是p和q，可以说明root是它们的公共祖先，但能确定root就是「最近」公共祖先吗？这就是一个巧妙的地方了，因为这里是二叉树的后序遍历！前序遍历可以理解为是从上往下，而后序遍历是从下往上，就好比从p和q出发往上走，第一次相交的节点就是这个root，也当然是最近公共祖先！

时间复杂度：O(N)，其中N 是二叉树的节点数。二叉树的所有节点有且只会被访问一次，因此时间复杂度为 O(N)。

空间复杂度：O(N)，其中N 是二叉树的节点数。递归调用的栈深度取决于二叉树的高度，二叉树最坏情况下为一条链，此时高度为 N，因此时间复杂度为 O(N)。

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    // base case:
    // 1. 如果是叶子节点的子节点(null)返回null
    // 2. 如果遇到p 或者 q 直接返回他们
    if (root == null){
        return null;
    }
    if (root == p || root ==q){
        return root;
    }

    // 左右子树返回的信息，后序遍历框架
    TreeNode left = lowestCommonAncestor(root.left, p, q);
    TreeNode right = lowestCommonAncestor(root.right, p, q);

    // 加工处理左右信息
    // 1. 如果左不为空，右不为空，则返回root，因为p，q恰好分布在左右两边
    // 此时root就是他们的最近公共父节点
    if (left != null && right != null){
        return root;
    }
    // 如果左为空，则返回右，p，q都在右子树中
    if (left == null){
        return right;
    }
    // 同理，如果右为空，则返回左，p，q都在左子树中
    if (right == null){
        return left;
    }
    // 左右子树没有，则返回空
    return null;
}

2.批量查询方法

先花较大的力气建立一种记录，以后执行每次查询时就可以完全根据记录进行查询。

利用层次遍历，记录每个节点和它的父节点，用哈希表建立映射关系
当要查询时，从node1开始，把node1自身和其所有的祖先节点放入一个无序集合中，最后一个祖先是根节点，他的祖先是null
从node2开始，检查node2是否在之前无序集合中，如果没有node2更新为它的父节点再检查
最后返回node2，就是lowest Common ancestor

比如我们在下图中，查询node(4)和node(8)的LCA

图片说明

节点	父节点
Node 8	Node 7
Node 7	Node 3
Node 6	Node 3
Node 5	Node 2
Node 4	Node 2
Node 3	Node 1
Node 2	Node 1
Node 1	Null

其中node(4)的父节点路径是APath(4) = {4, 2, 1}，然后node(8)去在这个路径中查询自己，第一次不在，查询node(8)的父节点node(7)，也不在，依次向上查询，最后找到node(1)！

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

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null){
        return null;
    }
    // 建立祖先查询表
    HashMap<TreeNode, TreeNode> ancestorMap = new HashMap<>();
    // 建立单个节点查询表
    HashSet<TreeNode> ancestorPath = new HashSet<>();
    // 建立辅助队列，进行层次遍历
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    // 根节点的祖先是 null
    ancestorMap.put(root, null);

    // 制作查询表
    while(!queue.isEmpty()){
        root = queue.poll();
        if (root.left!=null){
            queue.offer(root.left);
            ancestorMap.put(root.left, root);
        }
        if (root.right!=null){
            queue.offer(root.right);
            ancestorMap.put(root.right, root);
        }
    }

    // 制作单个节点的 祖先路径
    TreeNode path = p;
    while (path != null){
        ancestorPath.add(path);
        // 依次把p 和 p的所有祖先节点放入set中
        path = ancestorMap.get(path);
    }
    // 查询节点
    path = q;
    while (!ancestorPath.contains(path)){
        path = ancestorMap.get(path);
    }
    return path;
}

BST的LCA

力扣235二叉搜索树的最低公共祖先

上面介绍了普通二叉树的LCA，结下来利用BST的性质，可以更快速的求解。

解题思路：

我们从根节点开始遍历
如果待查询的两个节点的值都大于根节点，说明这两个节点在右子树，则在左子树中寻找
如果待查询的两个节点的值都小于根节点，说明这两个节点在右子树，则在左子树中寻找
如果当前节点的值不满足上述两条要求，那么说明当前节点就是「分岔点」。此时这两个节点要么在当前节点的不同的子树中，要么其中一个就是当前节点。返回分岔点就是答案。

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null){
        return null;
    }
    while (true){
        if (p.val > root.val && q.val > root.val){
            root = root.right;
        }
        else if (p.val < root.val && q.val < root.val){
            root = root.left;
        }else {
            break;
        }
    }
    // 跳出循环时，说明p，q均匀分布在左右子树，或者有一个在根，另一个在其子树上
    return root;
}

转化成累加树

力扣538. 把二叉搜索树转换为累加树

给出二叉搜索树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。

解题思路：

观察给出的实例图片可知，从大到小降序打印 BST 节点的值，如果维护一个外部累加变量sum，然后把sum赋值给 BST 中的每一个节点，就可以将 BST 转化成累加树。

public TreeNode convertBST(TreeNode root) {
    if (root == null){
            return null;
        }
        convertBST_process(root);
        return root;
}

int sum = 0;
public void convertBST_process(TreeNode root) {
    if (root == null){
        return;
    }
    // 传统中序遍历的倒叙
    convertBST_process(root.right);
    sum += root.val;
    root.val = sum;
    convertBST_process(root.left);
}

非递归框架：

public TreeNode convertBST(TreeNode root) {
    if (root == null){
        return null;
    }
    // 借助辅助栈
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode node = root;
    int sum = 0;
    while (!stack.isEmpty() || node!=null){
        if (node != null){
            stack.push(node);
            node = node.right;
        }else {
            node = stack.pop();
            sum += node.val;
            node.val = sum;
            node = node.left;
        }
    }
    return root;
}

二叉树(力扣)

0. 框架模型

a. 向左右子树要信息的框架

b. 一次性遍历一层的层次遍历

c. BST的框架

1. 递归框架

1.1 采用基本框架

二叉树镜像

1.2 单独考虑根节点

直径的二叉树

1.3 复杂度优化

完全二叉树的节点个数

1.4 层次遍历是更好解法

BT的最大宽度

2. 序列化框架

2.1 前中后序遍历

2.2 层次遍历

2.3 应用

寻找重复的子树

3. 重建二叉树

4. 二叉搜索树

4.1 增删改查

BST的第K大节点

BST的第K小节点

BST的搜索

BST的插入

BST的删除

4.2 利用BST的性质

验证BST

最低公共祖先

BST的LCA

转化成累加树