算法
AVL, 树, 算法

二叉搜索树

左子树上所有节点的值均小于根节点的值，而右子树上所有结点的值均大于根节点的值。故二叉搜索树中序遍历是单调递增的。

插入的序列越接近有序，生成的二叉搜索树就越像一个链表，为了避免二叉搜索树变成链表，故引入了平衡二叉树，即让树的结构看起来尽量均匀，左右子树的节点数尽量一样多。

生成平衡二叉树时，先按照生成二叉搜索树的方法构造二叉树，再根据插入的导致二叉树不平衡的节点位置进行调整，有LL左旋、RR右旋、LR先左旋后右旋、RL先右旋后左旋四种调整方式。

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
public class BinaryNode {
   int data;
   BinaryNode left;
   BinaryNode right;
   BinaryNode parent;

   public BinaryNode(int data) {
      this.data = data;
      this.left = null;
      this.right = null;
      this.parent = null;
   }
}
public class BinarySearchTree {
    /**
     * 查找数据
     */
    public BinaryNode find(BinaryNode root, int key) {
        BinaryNode current = root;
        while (current != null) {
            if (key < current.data) {
                current = current.left;
            } else if (key > current.data) {
                current = current.right;
            } else {
                return current;
            }
        }
        return null;
    }

    /**
     * 插入数据
     */
    public void insert(BinaryNode root, int data) {
        if (root.data < data) {
            if (root.right != null) {
                insert(root.right, data);
            } else {
                BinaryNode newNode = new BinaryNode(data);
                newNode.parent = root;
                root.right = newNode;

            }
        } else {
            if (root.left != null) {
                insert(root.left, data);
            } else {
                BinaryNode newNode = new BinaryNode(data);
                newNode.parent = root;
                root.left = newNode;
            }
        }
    }

    /**
     * 查找node的后继节点，若右子树为null，则返回当前节点作为后继节点
     */
    public BinaryNode finSuccessor(BinaryNode node) {
        if (node.right == null) { // 表示没有右边 那就没有后继
            return node;
        }
        BinaryNode cur = node.right;
        BinaryNode pre = node.right; // 开一个额外的空间用来返回后继节点，因为要找到为空的时候，那么其实返回的是上一个节点
        while (cur != null) {
            pre = cur;
            cur = cur.left; // 注意后继节点是要往左边找，因为右边的肯定比左边的大，要找的是第一个比根节点小的，所以只能往左边
        }
        return pre; // 因为cur会变成null，实际是要cur的上一个点，所以就是pre来代替
    }

    /**
     * 删除节点值为data的节点
     */
    public BinaryNode remove(BinaryNode root, int data) {
        BinaryNode delNode = find(root, data);
        if (delNode == null) {
            System.out.println("要删除的值不在树中");
            return root;
        }
        // 1.删除的点没有左右子树
        if (delNode.left == null && delNode.right == null) {
            if (delNode == root) { // 若删除的就是根节点，且根节点左右节点都为null
                root = null;
            } else if (delNode.parent.data < delNode.data) {
                delNode.parent.right = null;    // 删除节点是右节点
            } else {
                delNode.parent.left = null;    // 删除节点是左节点
            }
        } else if (delNode.left != null && delNode.right != null) { // 2.删除的节点有两颗子节点
            BinaryNode successor = finSuccessor(delNode); // 从右子树上找的后继节点，若右子树为null，则返回当前delNode节点，但明显不可能
            // 后继节点和删除节点进行交换，首先后继节点的左节点是肯定为空的，将删除节点的左子树放到后继节点的左子树上
            successor.left = delNode.left; // 后继的左边变为删除的左边，由于后继节点从右子树上找的，故这里的successor.left一开始肯定为null
            successor.left.parent = successor; // 删除点的左边parent指向后继节点
            // 再来看后继节点的右边
            if (successor.right != null && successor.parent != delNode) { // 后继节点有右边，这其实就是下面情况3的第一种
                successor.right.parent = successor.parent;
                successor.parent.left = successor.right;
                successor.right = delNode.right;
                successor.right.parent = successor;
            } else if (successor.right == null) {    // 若后继节点没有右边，那其实就是情况1，没有左右子树
                if (successor.parent != delNode) {        // 若后继节点的parent不等于删除的点 那么就需要把删除的右子树赋值给后继节点
                    successor.parent.left = null;        // 注意原来的后继节点上的引用要删掉，否则会死循环
                    successor.right = delNode.right;
                    successor.right.parent = successor;
                }
            }
            // 替换做完接下来就要删除节点了
            if (delNode == root) {
                successor.parent = null;
                return successor;
            }
            successor.parent = delNode.parent;
            if (delNode.data > delNode.parent.data) { // 删除的点在右边，关联右子树
                delNode.parent.right = successor;
            } else {
                delNode.parent.left = successor;
            }

        } else { // 3.删除点有一个节点
            if (delNode.right != null) { // 有右节点
                if (delNode == root) {
                    return delNode.right;
                }
                delNode.right.parent = delNode.parent; // 把右节点的parent指向删除点的parent
                // 关联父节点的左右子树
                if (delNode.data < delNode.parent.data) {
                    delNode.parent.left = delNode.right;  // 删除的点在左边
                } else {
                    delNode.parent.right = delNode.right;  // 删除的点在右边
                }
            } else { // 有左节点
                if (delNode == root) {
                    return delNode.left;
                }
                delNode.left.parent = delNode.parent;
                if (delNode.data < delNode.parent.data) {
                    delNode.parent.left = delNode.left;  // 删除的点在左边
                } else {
                    delNode.parent.right = delNode.left;  // 删除的点在右边
                }
            }
        }
        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
28
29
30
31
32
33
34
35
public Integer min;

public boolean isValidBST(TreeNode root) {
    if (root == null) {
        return true;
    }
    boolean left = isValidBST(root.left);
    if (!left || min != null && root.val <= min) {
        return false;
    }
    min = root.val;
    return isValidBST(root.right);
}

public boolean isValidBSTDfs(TreeNode root) {
    if (root == null) {
        return true;
    }
    Stack<TreeNode> stack = new Stack<>();
    TreeNode node = root;
    Integer min = null;
    while (node != null || !stack.isEmpty()) {
        while (node != null) {
            stack.add(node);
            node = node.left;
        }
        node = stack.pop();
        if (min != null && node.val <= min) {
            return false;
        }
        min = node.val;
        node = node.right;
    }
    return true;
}

二叉搜索树插入

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

删除节点

  • 若key > root.val，说明要删除的节点在右子树，root.right = deleteNode(root.right, key)。
  • 若key < root.val，说明要删除的节点在左子树，root.left = deleteNode(root.left, key)。
  • 若key == root.val，则该节点就是我们要删除的节点，则：
    • 若该节点是叶子节点，直接删除：root = null。
    • 若该节点不是叶子节点且有右节点，则用其后继节点值替代root.val = successor.val，然后删除后继节点。
    • 若该节点不是叶子节点且只有左节点，则用它的前驱节点值替代root.val = predecessor.val，然后删除前驱节点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public 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 {
        if (root.left == null && root.right == null) {
            root = null;
        } else if (root.right != null) {
            root.val = successor(root);
            root.right = deleteNode(root.right, root.val);
        } else {
            root.val = predecessor(root);
            root.left = deleteNode(root.left, root.val);
        }
    }
    return root;
}

后继节点，中序遍历序列的下一个节点。即比当前节点大的最小节点，先取当前节点的右节点，然后一直取该节点的左节点，直到左节点为空，则最后指向的节点为后继节点。

1
2
3
4
5
6
7
public int successor(TreeNode root) {
    root = root.right;
    while (root.left != null) {
        root = root.left;
    }
    return root.val;
}

前驱节点，中序遍历序列的前一个节点。即比当前节点小的最大节点，先取当前节点的左节点，然后取该节点的右节点，直到右节点为空，则最后指向的节点为前驱节点。

1
2
3
4
5
6
7
public int predecessor(TreeNode root) {
    root = root.left;
    while (root.right != null) {
        root = root.right;
    }
    return root.val;
}

将树转换成链表

cursor只是做一个引用传递，不断的将节点的right节点更新，然后将当前游标置为新节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
TreeNode cursor;
public TreeNode increasingBST(TreeNode root) {
    TreeNode ans = new TreeNode(0);
    cursor = ans;
    inorder(root);
    return ans.right;
}

public void inorder(TreeNode node) {
    if (node == null) {
        return;
    }
    inorder(node.left);
    node.left = null;
    cursor.right = node;
    cursor = node;
    inorder(node.right);
}

二叉搜索树降序遍历

1
2
3
4
5
6
7
8
public void convertBST(TreeNode root) {
    if (root == null) {
        return;
    }
    convertBST(root.right);
    System.out.println(root);
    convertBST(root.left);
}

最近公共祖先

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

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    // 保证 p.val < q.val
    if (p.val > q.val) {
        TreeNode tmp = p;
        p = q;
        q = tmp;
    }
    while (root != null) {
        // p,q 都在 root 的右子树中
        if (root.val < p.val) {
            // 遍历至右子节点
            root = root.right;
            // p,q 都在 root 的左子树中
        } else if (root.val > q.val) {
            // 遍历至左子节点
            root = root.left;
        } else {
            break;
        }
    }
    return root;
}

修剪二叉搜索树

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

前序结果构建树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int index = 0;
public TreeNode bstFromPreorder(int[] preorder) {
    if (preorder == null || preorder.length == 0) {
        return null;
    }
    return generateTree(preorder, Integer.MIN_VALUE, Integer.MAX_VALUE);
}

public TreeNode generateTree(int[] preorder, int lower, int upper) {
    if (index == preorder.length) {
        return null;
    }
    int rootVal = preorder[index];
    if (rootVal > upper || rootVal < lower) {
        return null;
    }
    index++;
    TreeNode root = new TreeNode(rootVal);
    root.left = generateTree(preorder, lower, rootVal);
    root.right = generateTree(preorder, rootVal, upper);
    return root;
}

后序结果构建树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int index = 0;
public TreeNode bstFromPostorder(int[] postorder) {
    if (postorder == null || postorder.length == 0) {
        return null;
    }
    return generateTree(postorder, Integer.MIN_VALUE, Integer.MAX_VALUE);
}

public TreeNode generateTree(int[] postorder, int lower, int upper) {
    if (index == postorder.length) {
        return null;
    }
    int rootVal = postorder[index];
    if (rootVal > upper || rootVal < lower) {
        return null;
    }
    index++;
    TreeNode root = new TreeNode(rootVal);
    root.right = generateTree(postorder, rootVal, upper);
    root.left = generateTree(postorder, lower, rootVal);
    return root;
}