⼆叉树算法的设计的总路线：明确⼀个节点要做的事情，然后剩下的事抛给框架。
⼆叉搜索树（Binary Search Tree，简称 BST）是⼀种很常⽤的的⼆叉树。它的定义是：⼀个⼆叉树中，任意节点的值要⼤于左⼦树所有节点的值，且要⼩于右边⼦树的所有节点的值。
二叉搜索树的中序遍历是一个升序的排序
查找效率最好O(logn)，最坏O(n)，插入效率和查找效率相同（只插入叶子节点）
实现
实现 BST 的基础操作：判断 BST 的合法性、增、删、查。其中“删”和“判断合法性”略微复杂。
零、判断 BST 的合法性
1
2
3
4
5
6
7
8
9
10
boolean isValidBST(TreeNode root) {
return isValidBST(root, null, null);
}
boolean isValidBST(TreeNode root, TreeNode min, TreeNode max) {
if (root == null) return true;
if (min != null && root.val <= min.val) return false;
if (max != null && root.val >= max.val) return false;
return isValidBST(root.left, min, root)
&& isValidBST(root.right, root, max);
}
在 BST 中查找⼀个数是否存在
1
2
3
4
5
6
7
8
9
10
boolean isInBST(TreeNode root, int target) {
if (root == null) return false;
if (root.val == target)
return true;
if (root.val < target)
return isInBST(root.right, target);
if (root.val > target)
return isInBST(root.left, target);
// root 该做的事做完了，顺带把框架也完成了，妙
}
插入
- 若二叉树为空，则首先单独生成根结点。
- 首先执行查找算法，找出被插结点的父亲结点。
- 判断被插结点是其父亲结点的左、右儿子。将被插结点作为叶子结点插入。
注意：新插入的结点总是叶子结点。
1
2
3
4
5
6
7
8
9
10
11
TreeNode insertIntoBST(TreeNode root, int val) {
// 找到空位置插⼊新节点
if (root == null) return new TreeNode(val);
// if (root.val == val)
// BST 中⼀般不会插⼊已存在元素
if (root.val < val)
root.right = insertIntoBST(root.right, val);
if (root.val > val)
root.left = insertIntoBST(root.left, val);
return root;
}
删除
首先找到⽬标节点，⽐⽅说是节点 P，如何删除这个节点，这是难点。因为删除节点的同时不能破坏 BST 的性质。
- 若 P 结点为叶子结点，即 PL(左子树)和 PR(右子树)均为空树。由于删去叶子结点不破坏整棵树的结构，则可以直接删除此子结点。
- 若 P 结点只有左子树 PL 或右子树 PR，此时只要令 PL 或 PR 直接成为其双亲结点 F 的左子树（当P是左子树）或右子树（当 P 是右子树）即可，此修改也不破坏二叉排序树的特性。
- 若 P 结点的左子树和右子树均不空。在删去 P 之后，为保持其它元素之间的相对位置不变，可按中序遍历保持有序进行调整，可以有两种做法：
- 其一是令 P 的左子树为 F 的左/右(依 P 是 F 的左子树还是右子树而定)子树，S 为 P 左子树的最右下的结点，而 P 的右子树为 S 的右子树，
- 其二是 P 的直接前驱（或直接后继）替代 P，然后再从二叉排序树中删去 直接前驱（或直接后继）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
TreeNode deleteNode(TreeNode root, int key) {
if (root == null) return null;
if (root.val == key) {
// 这两个 if 把情况 1 和 2 都正确处理了
if (root.left == null) return root.right;
if (root.right == null) return root.left;
// 处理情况 3
TreeNode minNode = getMin(root.right);
root.val = minNode.val;
root.right = deleteNode(root.right, minNode.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;
}
TreeNode getMin(TreeNode node) {
// BST 最左边的就是最⼩的
while (node.left != null) node = node.left;
return node;
}
删除操作就完成了。注意⼀下，这个删除操作并不完美，因为⼀般不会通过 root.val = minNode.val 修改节点内部的值来交换节点，⽽是通过⼀系列略微复杂的链表操作交换 root 和 minNode 两个节点。因为具体应⽤中，val 域可能会很⼤，修改起来很耗时，⽽链表操作⽆⾮改⼀改指针，⽽不会去碰内部数据。
