基本概念

什么叫二叉搜索树？
1、树节点增加key属性，用来比较谁大谁小，key不可以重复
2、对于任意一个树节点，它的key比左子树的key都大，同时也比右子树的key都小

最优情况的二叉搜索树是左右子树差不多平衡，时间复杂度为O(logn)
最差的情况是左右子树少了一边，又变成线性结构，此时时间复杂度为O(n)

算法实现

这里真的学了好久，也学了好多东西，停滞了好久哈哈哈，我把一些重要的贴上来

存储关键字和对应值(新增)

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
/**
 * <h2>存储关键字和对应值</h2>
 * @param key-关键字
 * @param value-值
 */
public void put(int key, Object value) {
    //1、key 如果key已经有了，就更新value
    BSTNode node = root;
    //再加一个变量记录父亲值
    BSTNode parent = null;
    while(node != null) {
        parent = node;
        if (node.key < key) {
            //在左子树找
            node = node.left;
        } else if (node.key > key) {
            //在右子树找
            node = node.right;
        } else {
            //找到了，更新
            node.value = value;
            //直接结束方法
            return;
        }
    }
    //2、key 没有 新增
    if(parent == null) { // 一开始就是空树，新增的就变成根节点了
        root = new BSTNode(key, value);
        return;
    }
    if(key < parent.key) {
        //作为左孩子
        parent.left = new BSTNode(key, value);
    } else {
        //作为右孩子
        parent.right = new BSTNode(key, value);
    }
}

找二叉搜索树前任

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
/**
 * <h2>查找关键字的前任</h2>
 * @param key-关键字
 * @return 前驱值
 */
public Object successor(int key) {
    BSTNode p = root;
    //祖先节点
    BSTNode ancestorFromLeft = null;
    while(p != null) {
        if(key < p.key) {
            p = p.left;
        } else if (key > p.key) {
            ancestorFromLeft = p;
            p = p.right;
        } else {
            break;
        }
    }
    //没找到对应节点
    if(p == null) {
        return null;
    }
    //找到了 情况1、节点有左子树，此时前任就是左子树的最大值
    if(p.left != null) {
        return max(p.left);
    }
    //找到节点 情况2、节点没有左子树，若离他最近的、自左而来的祖先就是前任
    return ancestorFromLeft != null ? ancestorFromLeft.value : null;
}

找二叉搜索树后继

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
/**
 * <h2>查找关键字的后继值</h2>
 * @param key-关键字
 * @return 后继值
 */
public Object predecessor(int key) {
    BSTNode p = root;
    //祖先节点
    BSTNode ancestorFromRight = null;
    while(p != null) {
        if(key < p.key) {
            ancestorFromRight = p;
            p = p.left;
        } else if(key > p.key) {
            p = p.right;
        } else {
            break;
        }
    }
    //循环结束如果p是null那么就没找到对应的值
    if(p == null) {
        return null;
    }
    //代码到这里表示找到了，要寻找它的后驱值
    //情况一：该节点有右子树，那么右子树中节点的最小值就是后继值
    if(p.right != null) {
        return getMin2(p.right);
    }
    //情况二：该节点没有右子树，那么离它最近的，自右向左来的祖先就是他的后继值
    return ancestorFromRight != null ? ancestorFromRight.value : null;
}

根据关键字删除(非递归递归)

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
/**
 * <h2>根据关键字删除</h2>
 * @param key-关键字
 * @return 被删除关键字的对应值
 */
public Object delete(int key) {
    BSTNode p = root;
    BSTNode parent = null;
    while(p != null) {
        if(key < p.key) {
            parent = p;
            p = p.left;
        } else if (key > p.key) {
            parent = p;
            p = p.right;
        } else {
            break;
        }
    }
    //循环结束判断是否找到
    if(p == null) {
        return null;
    }
    //删除操作
    if(p.left == null) {
        //情况1、删除节点没有左孩子，将右孩子托孤给Parent,左右孩子都没有也可以成立
        shift(parent, p, p.right); //没有左孩子顶上去的就是右孩子
    } else if(p.right == null) {
        //情况2、删除节点没有右孩子，将左孩子托孤给Parent,左右孩子都没有也可以成立
        shift(parent, p, p.left);
    } else {
        //情况四
        //4、1被删除节点找后继
        BSTNode s = p.right;
        BSTNode sParent = p;
        while(s.left != null) {
            sParent = s;
            s = s.left;
        }
        //循环结束后继节点即为s
        //4、2删除和后继不相等，处理后继的后事
        if(sParent != p) {
            //说明他们不相邻,处理后继的后事
            shift(sParent, s, s.right);
            s.right = p.right;
        }
        //4、3后继取代被删除节点
        shift(parent, p, s);
        s.left = p.left;
    }
    return p.value;
}

/**
 * <h2>托孤方法</h2>
 * @param parent-被删除节点的父亲
 * @param deleted-被删除的节点
 * @param child-被删除节点的孩子
 */
private void shift(BSTNode parent, BSTNode deleted, BSTNode child) {
    //若被删除的节点就是root
    if(parent == null) {
        //孩子变成根节点
        root = child;
    } else if (deleted == parent.left) {
        parent.left = child;
    } else if (deleted == parent.right) {
        parent.right = child;
    }
}

递归版本

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
/**
 * <h2>递归版删除节点</h2>
 * @param node-起点
 * @param key-关键字
 * @return 删剩下的孩子或null
 */
private BSTNode doDelete(BSTNode node, int key) {
    if(node == null) {
        return null;
    }
    if(key < node.key) {
        node.left = doDelete(node.left, key);//等于返回值
        return node;
    }
    if(node.key < key) {
        node.right = doDelete(node.right, key);
        return node;
    }
    //情况一 - 只有右孩子
    if(node.left == null) {
        return node.right;
    }
    //情况二 - 只有左孩子
    if(node.right == null) {
        return node.left;
    }
    //情况三 - 有两个孩子
    BSTNode s = node.right;
    while(s.left != null) {
        s = s.left;
    }
    //这一步是找到后继值但是不在待删除值的左右孩子情况
    doDelete(s.right, s.key);
    s.left = node.left;
    return s;
}

根据关键字范围查询

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
/**
 * <h2>找 >= key1 且 <= key2 的所有value</h2>
 * @param key1-小关键字
 * @param key2-大关键字
 * @return 结果集合
 */
public List<Object> between(int key1 , int key2) {
    //二叉搜索树的中序遍历就是升序排序，然后把符合条件的存入集合即可
    ArrayList<Object> result = new ArrayList<>();
    //迭代法求中序遍历
    BSTNode p = root;
    //使用迭代法必须用栈
    LinkedList<BSTNode> stack = new LinkedList<>();
    while (p != null || stack.isEmpty()) { //向前进 || 向后退
        if(p != null) {
            stack.push(p);
            p = p.left;
        } else {
            //开始向回走
            BSTNode pop = stack.pop();
            // 处理这个值
            if(key1 >= pop.key && key2 <= pop.key) {
                result.add(pop.value);
            } else if (pop.key > key2) {
                break;
            }
            //向右走
            p = pop.right;
        }
    }
    return result;
}

力扣题目合集

力扣450-删除节点

见力扣上代码哈哈哈

力扣701-新增节点

递归版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public TreeNode insertIntoBST(TreeNode root, int val) {
    //递归版
    if(root == null) {
        //到了节点为空的地方就是我们要插入的地方
        return new TreeNode(val);
    }
    if(root.val < val) {
        //建立父子关系
        root.right = insertIntoBST(root.right, val);
    } else {
        //建立父子关系
        root.left = insertIntoBST(root.left, val);
    }
    return root;
}

力扣700-查询节点

递归版本

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

力扣98-验证合法二叉搜索树

简单的方法就是中序遍历如果是升序的那么就是合法的
下面的是递归剪枝方法，很牛

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
long prev = Long.MIN_VALUE;

public boolean isValidBST(TreeNode root) {
    //递归中序遍历
    if(root == null) {
        return true;
    }
    //左右子树也得符合
    boolean a = isValidBST(root.left);
    //如果左子树判断有失败的就直接返回false了
    //第一次接触剪枝代码
    if(!a) {
        return false;
    }
    //当前值判断
    if(prev >= root.val) {
        return false;
    }
    prev = root.val;
    return isValidBST(root.right);
}

力扣938-二叉搜索树范围和

还是d递归剪枝方法，其它方法都很简单

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int rangeSumBST(TreeNode root, int low, int high) {
    //上下限递归
    if(root == null) {
        return 0;
    }
    if(root.val < low) {
        //剪掉左子树
        return rangeSumBST(root.right, low, high);
    }
    if(root.val > high) {
        //剪掉右子树
        return rangeSumBST(root.left, low, high);
    }
    //在范围内
    return root.val + rangeSumBST(root.left, low, high) + rangeSumBST(root.right, low, high);
}

力扣1008-前序遍历构造二叉搜索树

递归分而治之法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 public TreeNode bstFromPreorder(int[] preorder) {
    //分而治之解法
    return fenerzhizhi(preorder, 0, preorder.length - 1);
}
private TreeNode fenerzhizhi(int[] preorder, int start, int end) {
    if(start > end) {
        //这代表数组内没有元素了，递归结束
        return null;
    }
    //首先找到根节点
    TreeNode root = new TreeNode(preorder[start]);
    int index = start + 1;
    while(index <= end) {
        if(preorder[start] < preorder[index]) {
            break;
        }
        index++;
    }
    //递归插入
    root.left = fenerzhizhi(preorder, start + 1, index - 1);
    root.right = fenerzhizhi(preorder, index, end);
    return root;
}

力扣235-二叉搜索树最近公共祖先

1
2
3
4
5
6
7
8
9
10
11
12
13
14
待查找点p q 在某一个结点的两侧，那么此节点就是最近的公共祖先
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    //待查找点p q 在某一个结点的两侧，那么此节点就是最近的公共祖先
    TreeNode a = root;
    while(p.val < a.val && q.val < a.val || p.val > a.val && q.val > a.val) {
        //在同一侧
        if(p.val < a.val) {
            a = a.left;
        } else {
            a = a.right;
        }
    }
    return a;
}