模板题目链接

• BST查找 - Leetcode 270. Closest BST Value
• BST插入 - Leetcode 701. Insert Node in BST
• BST删除 - Leetcode 450. Delete Node in BST

二叉搜索树-BST 概述

BST是二叉树的一种，具备二叉树的结构性质：只有一个Root节点，每一个节点最多可以有左右两个子节点。BST自身的性质：每一个节点的左儿子数值一定比他小，右儿子的数值一定比他大。这个性质也使得BST的中序遍历输出结果是一个严格递增序列。严格意义上，BST中不保存数值相同的元素，如果有重复元素可以在每一个节点加入count属性来进行计数。

BST基本问询模板

• 查找一个元素

根据BST左右子节点大小关系，可以直接使用二分法进行数值查询，如果当前数值比查找数值小，那么往左边找，反之往右边找。

代码如下：

class Solution {double min = Double.MAX_VALUE;int res = -1;public int closestValue(TreeNode root, double target) {search(root, target);return res;}private void search(TreeNode root, double target) {// > target的第一个数if(root==null) return;if(Math.abs(root.val-target)<min) {min = Math.abs(root.val-target);res = root.val;}if(root.val>target) search(root.left, target);search(root.right, target);}}

时间复杂度：, 如果BST结构较为平衡(最大高度差<=1)也就是平衡BST的情况下,最坏的情况是有可能BST结构非常不平衡，也就是所有节点形成类似链表结构，这时时间会是；空间复杂度：也就是递归深度。 

•    BST插入节点

插入节点思路比较好理解，我们先根据大小关系找到要插入的数值能插入的叶子节点位置，并建立新的节点与BST接上即可

 

代码如下： 

class Solution {public TreeNode insertIntoBST(TreeNode root, int val) {TreeNode res = insert(root, val);return res;}private TreeNode insert(TreeNode root, int val){// 分治if(root==null) return new TreeNode(val);if(root.val<val) root.right = insert(root.right, val);else if(root.val>val) root.left = insert(root.left, val);return root;}
}

• 删除节点 

删除节点是基本问询中最复杂的一个，因为当删除某个元素时，为了维护BST的有序性质，需要找一个节点来顶替删除节点位置，并且保证顶替后依然是BST。

再删除节点时，有三种可能性：

1. 删除节点是叶子节点：这种情况直接将该节点删除即可
2. 删除节点只有左或者右儿子：这种情况就直接将删除节点左或右儿子直接接上即可
3. 删除节点有左右儿子：这种情况最为复杂，通常会找这两种节点作为顶替节点: 左子树中最大的那个点，或者右子树中最小的那个点 - 也就是删除点的前驱(predecessor)和后继节点(successor)。这两个点通常为叶子节点或者只有左或右儿子(因为他们本身是子树上最左和右的节点) 所以将该节点顶替到删除节点的位置后，直接将其左或者右子树接上去即可(如果有的话)。
   1. 左子树最大的点：也就是左子树最右边的那个点
   2. 右子树最小的点：也就是右子树最左边的那个点

 

代码如下：

class Solution {public TreeNode deleteNode(TreeNode root, int key) {TreeNode res = delete(root, key);return res;}private TreeNode delete(TreeNode root, int key) {if(root==null) return null;if(root.val<key) root.right = delete(root.right, key);else if(root.val>key) root.left = delete(root.left, key);else {// if root is leaf, directly removeif(root.left==null && root.right==null) {return null;} else if(root.left!=null && root.right!=null) {// find predecessor or successor to replace remove node// predecessor - 左边的最大值TreeNode left = root.left;if(left.right==null) {// no right node current node is predecessorroot.val = left.val;root.left = left.left;} else {// 向右找到最右也就是最大节点以及最大节点的parent// 这里使用快慢针来找到对应位置TreeNode fast = left.right;TreeNode slow = left;while(fast.right!=null) {fast = fast.right;slow = slow.right;}// fast 找到最右边，slow是上一个节点root.val = fast.val;slow.right = fast.left; // remove predecessor}return root;} else {// one side is not leafif(root.left!=null) return root.left;if(root.right!=null) return root.right;}}return root;}
}

时间复杂度：如果是平衡BST那么就是，最坏情况：；空间复杂度： 即递归深度。