Table of Contents

一、二叉搜索树代码框架

BST 是二叉排序树：根节点大于等于左子树所有节点，小于等于右子树所有节点。

二叉查找树中序遍历有序。

对于 BST 相关的问题，经常可以看到类似下面的代码逻辑：

1
2
3
4
5
6
7
8

void BST(TreeNode root, int target) {
    if (root.val == target)
        // 找到目标，做点什么
    if (root.val < target) 
        BST(root.right, target);
    if (root.val > target)
        BST(root.left, target);
}

二、基本操作

1. 搜索、查找元素

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

TreeNode searchBST(TreeNode root, int target) {
    if (root == null) return null;
    if (root.val > target) {
        return searchBST(root.left, target);
    }
    
   	if (root.val < target) {
        return searchBST(root.right, target);
    }
    return root;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

TreeNode searchBST(TreeNode root, int target) {
    TreeNode cur = root;
    while (cur != null) {
        if (target == cur.val) {
            return cur;
        } else if(target < cur.val) {
            cur = cur.left;
        } else {
            cur = cur.right;
        }
    }
    return null;
}

2. 插入元素

 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.left = insertIntoBST(root.left, val);
    } else if (val > root.val) {
        root.right = insertIntoBST(root.right, val);
    }
    return root;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

public TreeNode insertIntoBST(TreeNode root, int val) {
    TreeNode parent = null;
    TreeNode cur = root;
    while (cur != null) {
        parent = cur;
        if (val < cur.val) {
            cur = cur.left;
        } else if(val > cur.val) {
            cur = cur.right;
        }
    }
    if (parent == null) {
        return new TreeNode(val);
    }
    if (val < parent.val) {
        parent.left = new TreeNode(val);
    } else {
        parent.right = new TreeNode(val);
    }
    return root;
}

3. 删除操作

 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

public TreeNode deleteNode(TreeNode root, int key) {
    if (root == null) {
        return null;
    }
    if (root.val == key) {
        if (root.left == null) return root.right;
        if (root.right == null) return root.left;
        // 左右节点都不空
        TreeNode minNode = successor(root);
        root.val = minNode.val;
        root.right = deleteNode(root.right, minNode.val);
    } else if(root.val > key) {
        root.left = deleteNode(root.left, key);
    } else {
        root.right = deleteNode(root.right, key);
    }
    return root;
}

private TreeNode successor(TreeNode root) {
    // cur不为空
    TreeNode cur = root.right;
    while (cur.left != null) {
        cur = cur.left;
    }
    return cur;
}