二叉树1️⃣

刷二叉树

重要性就💝

​ 很多经典的算法，都是树的相关问题，点击这里有说明为什么。

​ 回归到树的问题，也就是回归到这几行代码之上。

1
2
3
4
5
6
7
8
/* 二叉树遍历框架 */
void traverse(TreeNode root) {
    // 前序遍历
    traverse(root.left)
    // 中序遍历
    traverse(root.right)
    // 后序遍历
}

​ 再说说经典算法 快速排序 归并排序，这其中，快速排序就是个二叉树的前序遍历，归并排序就是个二叉树的后序遍历。

​ 快速排序的逻辑：

​ 快速排序的逻辑是，若要对 nums[lo..hi] 进行排序，我们先找一个分界点 p，通过交换元素使得 nums[lo..p-1] 都小于等于 nums[p]，且 nums[p+1..hi] 都大于 nums[p]，然后递归地去 nums[lo..p-1] 和 nums[p+1..hi] 中寻找新的分界点，最后整个数组就被排序了。

1
2
3
4
5
6
7
8
9
void sort(int[] nums, int lo, int hi) {
    /****** 前序遍历位置 ******/
    // 通过交换元素构建分界点 p
    int p = partition(nums, lo, hi);
    /************************/

    sort(nums, lo, p - 1);
    sort(nums, p + 1, hi);
}

​ 归并排序逻辑：

​ 若要对 nums[lo..hi] 进行排序，我们先对 nums[lo..mid] 排序，再对 nums[mid+1..hi] 排序，最后把这两个有序的子数组合并，整个数组就排好序了。

1
2
3
4
5
6
7
8
9
10
void sort(int[] nums, int lo, int hi) {
    int mid = (lo + hi) / 2;
    sort(nums, lo, mid);
    sort(nums, mid + 1, hi);

    /****** 后序遍历位置 ******/
    // 合并两个排好序的子数组
    merge(nums, lo, mid, hi);
    /************************/
}

秘诀

写递归算法的关键是要明确函数的「定义」是什么，然后相信这个定义，利用这个定义推导最终结果，绝不要跳入递归的细节，脑袋里的栈根本就想不明白。

写树相关的算法，简单说就是，先搞清楚当前 root 节点该做什么，然后根据函数定义递归调用子节点，递归调用会让孩子节点做相同的事情。

相关练习

反转二叉树

相当于二叉树的前序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root == null){
            return null;
        }
        TreeNode temp = null;
        temp = root.left;
        root.left = root.right;
        root.right = temp;
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }
}

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

输入：root = [1,2,3,4,5,6,7]
输出：[1,#,2,3,#,4,5,6,7,#]
解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。序列化的输出按层序遍历排列，同一层节点由 next 指针连接，’#’ 标志着每一层的结束。

二叉树的问题难点在于，如何和将题目的要求细化到每个节点都需要做的事情。

解决方法就是添加辅助函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public Node connect(Node root) {
        if(root==null){
            return root;
        }
        connectTwoNode(root.left, root.right);
        return root;
    }
    public void connectTwoNode(Node left, Node right){
        if(left == null){
            return;
        }
        // 相当于前序遍历
        left.next = right;
        connectTwoNode(left.left, left.right);
        connectTwoNode(left.right, right.left);
        connectTwoNode(right.left, right.right);
    }
}

将二叉树展开成链表

其实就是一个后序遍历，先把左右节点拉直，在进行处理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    TreeNode newRoot;
    public void flatten(TreeNode root) {
        if(root==null){
            return;
        }
        flatten(root.left);
        flatten(root.right);

        TreeNode left = root.left;
        TreeNode right = root.right;

        root.left = null;
        root.right = left;

        TreeNode p = root;
        while(p.right != null){
            p = p.right;
        }
        p.right = right;
    }
}

根据中序后序遍历构造二叉树

根据中序遍历和后序遍历的特点，我们可以清楚地知道，中序是左根右，后序是左右根，所以根据此我们可以得到根节点，只要找到中心序遍历中节点的位置，再判断出左右子树的大小，进行递归，就解决啦。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        return build(inorder, 0, inorder.length-1, postorder, 0, postorder.length-1);
    }

    public TreeNode build(int[] inorder, int instart, int inend, int[] postorder, int poststart, int postend){
        if(instart>inend){
            return null;
        }
        //找到 inorder 节点位置
        int rootVal = postorder[postend];
        int leftSize = 0;
        int rootIndex = 0;
        for(int i=instart; i<=inend; i++){
            if(inorder[i]==rootVal){
                leftSize = i-instart;
                rootIndex = i;
                break;
            }
        }
        // 创建 root
        TreeNode root = new TreeNode(rootVal);
        // 递归建立左节点
        root.left = build(inorder, instart, rootIndex-1, postorder, poststart, poststart+leftSize-1);
        // 递归建立右节点
        root.right = build(inorder, rootIndex+1, inend, postorder, leftSize+poststart, postend-1);
        return root;
    }
}

这样看性能不是很好时间复杂度o()，空间复杂度o()，我们可以利用哈希表来进行根节点的定位，避免每一次递归中循环产生的额外时间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    private Map<Integer, Integer> map;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        map = new HashMap<Integer, Integer>();
        for(int i=0; i<inorder.length; i++){
            map.put(inorder[i], i);
        }
        return build(inorder, 0, inorder.length-1, postorder, 0, postorder.length-1);
    }

    public TreeNode build(int[] inorder, int instart, int inend, int[] postorder, int poststart, int postend){
        if(instart>inend || poststart>postend){
            return null;
        }
        //找到 inorder 节点位置
        int rootVal = postorder[postend];
        int rootIndex = map.get(rootVal);
        int leftSize = rootIndex-instart;
        // 创建 root
        TreeNode root = new TreeNode(rootVal);
        // 递归建立左节点
        root.left = build(inorder, instart, rootIndex-1, postorder, poststart, poststart+leftSize-1);
        // 递归建立右节点
        root.right = build(inorder, rootIndex+1, inend, postorder, leftSize+poststart, postend-1);
        return root;
    }
}

寻找重复子树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    List<TreeNode> result = new ArrayList<TreeNode>();
    Map<String, Integer> map = new HashMap<>();

    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        // 方法的意义就是 将本节点放入 map 中并返回字符串
        handle(root);
        return result;
    }

    public String handle(TreeNode root){
        if(root==null){
            return "#";
        }
        // 把自己是什么样子取出来
        String left = handle(root.left);
        String right = handle(root.right);
        String subTree = left+","+right+","+root.val;
        // 放到集合里面，并且统计次数
        int count = map.getOrDefault(subTree, 0);
        if(count==1){
            result.add(root);
        }
        map.put(subTree, count+1);
        return subTree;
    }
}

时间复杂度 O(N^2) 遍历二叉树节点 N，序列化时间N
空间复杂度 O(N^2) map 的大小

优化：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
```





#### 二叉树的序列化和反序列化



本质上来看就是二叉树的遍历

##### 前序遍历

1
2
3
4
5
6
7





##### 中序遍历

1
2
3
4
5
6
7





##### 后序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59





## 刷二叉搜索树💗



> 什么是 BST：
>
> 1. 对于 BST 的每一个节点 `node`，左子树节点的值都比 `node` 的值要小，右子树节点的值都比 `node` 的值大。
> 2. 对于 BST 的每一个节点 `node`，它的左侧子树和右侧子树都是 BST。
>
> 有哪些熟悉的数据结构是基于 BST 的呢？
>
>  AVL 树，红黑树等等，还有 B+ 树，线段树等结构，拥有了自平衡性质，可以提供 logN 级别的增删查改效率
>
> **从做算法题的角度来看 BST，除了它的定义，还有一个重要的性质：BST 的中序遍历结果是有序的（升序）**。



### 中序遍历





#### [BST第 k 小的元素](https://leetcode-cn.com/problems/kth-smallest-element-in-a-bst/)



思路：
升序排列，找到第 k 个数就可以了。

```java
class Solution {
    // 结果
    int result = 0;
    // 位置
    int index = 0;
    public int kthSmallest(TreeNode root, int k) {
        handle(root, k);
        return result;
    }
    public void handle(TreeNode root, int k){
        if(root==null){
            return;
        }
        handle(root.left, k);
        // 位置跳到此节点
        index++;
        if(k == index){
            result = root.val;
            return;
        }
        handle(root.right, k);
    }
}

但是仔细想想，这种方法的时间复杂度在最坏情况下去考虑是 o(N)，N 是 BST 节点的个数，但是红黑树之类的增删改查都是 o(logN) 的复杂度，所以我们来想想怎么改进。

来看看 o(logN) 的复杂度是怎样实现的？答案还是 BST 的定义，左子树小，右子树大，所以每个节点可以去对比自身的值来决定去哪边搜索。
举个例子，我想查找排名 k 的元素，而当前节点知道自己排第 m ，我们来比较 m 和 k 的大小。

  1. m==k 找到了，返回当前节点
  2. k<m 去左子树搜索第 k 个元素
  3. k>m 去右子树搜索第 k-m-1 个元素

怎么实现节点知道自己的排第几呢，需要在 TreeNode 中额外添加属性 int size;，记录以自己 为根的二叉树有多少个节点。

二叉搜索树转化累加树

根据题意去思考一下，思路很简单

利用了 BST 的特性，中序遍历有序，然后我们将中序遍历进行改造使他能够降序排列，然后取出值进行取和，然后把值替换，就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public TreeNode convertBST(TreeNode root) {
        handle(root);
        return root;
    }
    int sum = 0;
    public void handle(TreeNode root){
        if(root==null){
            return;
        }
        handle(root.right);
        sum += root.val;
        root.val = sum;
        handle(root.left);
    }
}

二叉搜索树的增删改以及验证合法性

删除二叉搜索树中的节点

​ 按照框架进行编写（注意修改链表的递归一定要进行赋值操作，否则不生效）

主函数意义：

删除这个树结构中所要查找的值。

分析细节：

  1. key 是叶子结点
  2. key 是结点但是有单边树
  3. key 是结点且有双边树
    • 此时我们的策略就是寻找当前后继结点或者前继结点，让最接近他的数值作为新的结点
    • 然后再进行替换与删除
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        if(null == root){
            return null;
        }
        if(root.val == key){
            // 找到了相应元素
            // 1. 叶子结点
            // 2. 一个空节点
            if(root.left == null){
                return root.right;
            }
            if(root.right == null){
                return root.left;
            }else{
                TreeNode minRoot = getMin(root.right);
                root.val = minRoot.val;
                root.right = deleteNode(root.right, minRoot.val);
            }
        }else if(root.val > key){
            root.left = deleteNode(root.left, key);
        }else if(root.val < key){
            root.right = deleteNode(root.right, key);
        }
        return root;
    }   
    public TreeNode getMin(TreeNode node){
        while(node.left != null){
            node = node.left;
        }
        return node;
    }
}

验证二叉搜索树

​ 就是要当前节点的左子树全比自己小，右子树全比自己大，左右子树都是二叉搜索树。

​ 注意哦！是左子树的所有节点的值都比 root 小，所以我们要对每一轮的验证中加入神定下来的铁律，就是增加限制最大值最小值的约束

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public boolean isValidBST(TreeNode root) {
        return judge(root, null, null);
    }

    public boolean judge(TreeNode root, TreeNode max, TreeNode min){
        if(root == null){
            return true;
        }
        // 判断基本条件
        if(min!=null && root.val <= min.val){
            return false;
        }else if(max!=null && root.val >= max.val){
            return false;
        }
        return judge(root.left, root, min) && judge(root.right, max, root);
    }
}

​ 通过添加辅助函数的方法增加约束，这是二叉搜索树的常用及技巧！！

二叉搜索树中的搜索

充分利用左小右大的特点！很简单

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        if(null == root){
            return null;
        }
        if(root.val == val){
            return root;
        }else if(root.val > val){
            return searchBST(root.left, val);
        }else if(root.val < val){
            return searchBST(root.right, val);
        }
        return null;
    }
}

二叉搜索树中的插入

插入自然而然的涉及到谁做根的问题，所以这种时候有不同的解法

第一种：常规算法

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if(null == root){
            return new TreeNode(val);
        }
        if(root.val > val){
            root.left = insertIntoBST(root.left, val);
        }else if(root.val < val){
            root.right = insertIntoBST(root.right, val);
        }
        return root;
    }
}

框架

所以对于 BST 的增删改查是有框架的

1
2
3
4
5
6
7
8
void BST(TreeNode root, int target) {
    if (root.val == target)
        // 找到目标，做点什么
    if (root.val < target) 
        BST(root.right, target);
    if (root.val > target)
        BST(root.left, target);
}

除此之外，如果当前节点会对下面的子节点有整体影响，可以通过辅助函数增长参数列表，借助参数传递信息。

验证 BST 合法性

不同的二叉搜索树①

题目相关描述自行点击 ☝ 链接

核心思想就是穷举，但是如何具体到每一个节点之上呢？

我们来看 [1,2,3,4,5] 这个数组，单看 3 这个节点，左右子树分别是 [1,2]，[4,5]。我们求出这个数组对应的 BST 数量，再进行相乘，就是 3 这个节点所对应的 BST 的数量，我们递归运算即可。每次递归出这个范围内的二叉树的数量。

但是递归之后计算时间复杂度发现，有太多重复运算的地方了，所以我们要加入一个备忘录，是什么样的数据结构来存储呢？

因为要存储的数据是 [1,2]，[1,3]，[4,5]，[3,5]，[2,4] 这样的数据，所以来说二维数组是一个不错的选择！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    int[][] bba;
    public int numTrees(int n) {
        bba = new int[n+1][n+1];
        return count(1, n);
    }

    public int count(int left, int right){
        if(left>right){
            return 1;
        }
        // 1. 首先在备忘录里查找
        if(bba[left][right] != 0){
            return bba[left][right];
        }
        // 2. 没查找到进行计算
        int result = 0;
        for(int i=left; i<=right; i++){
            int l = count(left, i-1);
            int r = count(i+1, right);
            result += l*r;
        }
        bba[left][right] = result;
        return result;
    }
}

不同的二叉搜索树②

题目相关描述自行点击 ☝ 链接

与上一题不同的是，本道题返回的是树节点的集合。但是大体思路都是一样的。

唯一不同之处在于，此题需要两层 for 循环去构造节点，而不能像刚才那样直接相乘。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
    
    public List<TreeNode> generateTrees(int n) {
        if(n==0){
            return new ArrayList<>();
        }
        return buildTrees(1, n);
    }

    public List<TreeNode> buildTrees(int left, int right){
        List<TreeNode> res = new ArrayList<>();
        // 1. basecase
        if(left > right){
            res.add(null);
            return res;
        }
        for(int i=left; i<=right; i++){
            List<TreeNode> leftTree = buildTrees(left, i-1);
            List<TreeNode> rightTree = buildTrees(i+1, right);
            for(TreeNode l : leftTree){
                for(TreeNode r : rightTree){
                    TreeNode root = new TreeNode(i);
                    root.left = l;
                    root.right = r;
                    res.add(root);
                }
            }
        }
        return res;
    }
}