0. 框架模型

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

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

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

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

写递归时的步骤如下，

1. 定义好Info结构体
2. 递归函数process的返回Info
3. base case也就是空树返回
4. 从左右子树要信息
5. 根据列出的可能性，把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. 二叉树的直径

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

示例 :
给定二叉树

      1
     / \
    2   3
   / \     
  4   5    

返回 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

递归套路思考：

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

递归解析：

1. 终止条件(base case):

   • 当到达叶子结点的子树时，返回Null
   • 当root=q / p时，返回根节点本身

2. 递推工作：

   • 开启递归左子节点，返回值记为 left
   • 开启递归右子节点，返回值记为 right

3. 整合规则：

   • 当左右子树的返回都是空，说明查询节点都不在左右子树上，则返回空
   • 当左右子树都不是空，说明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.批量查询方法

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

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

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

其中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的性质，可以更快速的求解。

解题思路：

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

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;
}