二叉搜索树（Binary Search Tree）是一种特殊形式的二叉树，节点值大于左子树小于右子树。因为这种性质，导致它的中序遍历为升序。
- 判断一颗二叉树是否为二叉搜索树
- 二叉搜索树迭代器
- 二叉搜索树查找
- 二叉搜索树插入
- 二叉搜索树删除
- 二叉搜索树查找第K大的节点
- 二叉搜索树在指定范围内查找符合条件的两个节点
- 二叉搜索树是否平衡
- 有序数组构造二叉搜索树
判断一颗二叉树是否为二叉搜索树
可以根据二叉搜索树的特性进行判断，节点值大于左子树小于右子树。
private boolean isValidBST(TreeNode root) {
if (root != null) {
//一直到最左的左叶子节点
if (!isValidBST(root.left)) return false;
//第一次执行到这里时pre为空
if (pre != null && root.val <= pre.val) return false;
//第一次为pre赋值的为最小的叶子节点
pre = root;
return isValidBST(root.right);
}
return true;
}
类似中序遍历
二叉搜索树迭代器
迭代器需要判断是否存在下一项，且按序迭代。
可以采用栈来完成，迭代器初始化时将根结点的所有左子树压栈，每次出栈时将出栈节点的所有右子树压栈。当栈为空时二叉搜索树迭代完成。
https://blog.csdn.net/smile_watermelon/article/details/47280679
class BSTIterator {
LinkedList<TreeNode> stack = new LinkedList<TreeNode>();
public BSTIterator(TreeNode root) {
TreeNode node = root;
//压入根结点及所有的左孩子节点
while (node != null) {
stack.push(node);
node = node.left;
}
}
public boolean hasNext() {
return !stack.isEmpty();
}
public TreeNode next() {
TreeNode node = stack.pop();//1、根结点出栈（根结点小于右节点）
TreeNode temp = node.right;
while (temp != null) {
stack.push(temp);//右节点入栈
temp = temp.left;//右节点的左节点入栈
}
//所以栈顶值最小
return node;
}
}
二叉搜索树查找
根据性质，小于根结点的去左子树去找，大于根结点的去右子树去找。
private TreeNode search(TreeNode root, int key) {
if (root == null) {
return null;
}
if (key < root.val) {
return search(root.left, key);
} else if (key > root.val) {
return search(root.right, key);
} else {
return root;
}
}
二叉搜索树插入
插入的节点必须符合二叉搜索树的性质
private TreeNode insert(TreeNode root, int key) {
if (root == null) {
return new TreeNode(key);
}
if (key < root.val) {
if (root.left == null) {
root.left = new TreeNode(key);
} else {
insert(root.left, key);
}
}
if (key > root.val) {
if (root.right == null) {
root.right = new TreeNode(key);
} else {
insert(root.right, key);
}
}
return root;
}
二叉搜索树删除
删除的节点如果是叶子节点，则直接删除。如果不是叶子节点，删除节点可能会导致树断掉，因此需要将删掉节点的子树连接到删掉节点的父节点上，且要保证连接后的二叉树为二叉搜索树。
private TreeNode delete(TreeNode root, int key) {
if (root == null) {
return null;
}
if (key < root.val) {
root.left = delete(root.left, key);
} else if (key > root.val) {
root.right = delete(root.right, key);
} else {
if (root.left == null) {
return root.right;
} else if (root.right == null) {
return root.left;
} else {
root.val = min(root.right);
root.right = delete(root.right, root.val);
}
}
return root;
}
private int min(TreeNode root) {
TreeNode node = root;
while (node != null && node.left != null) {
node = node.left;
}
return node.val;
}
二叉搜索树查找第K大的节点
由二叉搜索树的性质右子树大于节点，优先遍历右子树，遍历次数为K时返回节点。
https://www.geeksforgeeks.org/kth-largest-element-in-bst-when-modification-to-bst-is-not-allowed/
private void kThLargest(TreeNode node, int k) {
if (node == null || c > k) {
return;
}
kThLargest(node.right, k);
c++;
if (c == k) {
kThNode = node;
return;
}
kThLargest(node.left, k);
}
二叉搜索树在指定范围内查找符合条件的两个节点
使用到了TreeSet
set.floor(num)用于返回set中小于num的最大的项
set.ceiling(num)用于返回set中大于num的最小的项
private boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
if (nums == null || nums.length == 0) {
return false;
}
if (k <= 0 || t < 0) {
return false;
}
TreeSet<Integer> set = new TreeSet<Integer>();
for (int i = 0; i < nums.length; i++) {
int num = nums[i];
if ((set.floor(num) != null && num - set.floor(num) <= t)
|| set.ceiling(num) != null && set.ceiling(num) - num <= t) {
return true;
} else {
set.add(num);
}
if (i >= k) {//控制窗口大小
set.remove(nums[i - k]);
}
}
return false;
}
二叉搜索树是否平衡
平衡的条件是左右子树的高度差不大于1。
private boolean isBalance(TreeNode root) {
if (root == null) {
return true;
}
if (Math.abs(height(root.left) - height(root.right)) > 1) {
return false;
}
return isBalance(root.left) && isBalance(root.right);
}
private int height(TreeNode node) {
if (node == null) {
return 0;
}
int left = height(node.left);
int right = height(node.right);
return (left > right ? left : right) + 1;
}
有序数组构造二叉搜索树
有序数组中间节点为根结点，以此将一个数组分成两个数组。
将问题缩小，分而治之，明显的递归操作。
private TreeNode sortedArrayToBST(int[] nums) {
if (nums.length == 0) {
return null;
}
if (nums.length == 1) {
return new TreeNode(nums[0]);
}
int center = nums.length / 2;
TreeNode root = new TreeNode(nums[center]);
int[] left = new int[center];
int[] right = new int[nums.length - center - 1];
System.arraycopy(nums, 0, left, 0, center);
System.arraycopy(nums, center + 1, right, 0, nums.length - center - 1);
root.left = sortedArrayToBST(left);
root.right = sortedArrayToBST(right);
return root;
}
