二分查找树（Binary Search Tree）

一、BST 特性

1、对于 BST 的每一个节点 node，左子树节点的值都比 node 的值要小，右子树节点的值都比 node 的值大。

2、对于 BST 的每一个节点 node，它的左侧子树和右侧子树都是 BST。

二叉搜索树并不算复杂，但我觉得它可以算是数据结构领域的半壁江山，直接基于 BST 的数据结构有 AVL 树，红黑树等等，拥有了自平衡性质，可以提供 logN 级别的增删查改效率；还有 B+ 树，线段树等结构都是基于 BST 的思想来设计的。

从做算法题的角度来看 BST，除了它的定义，还有一个重要的性质：BST 的中序遍历结果是有序的（升序）。

也就是说，如果输入一棵 BST，以下代码可以将 BST 中每个节点的值升序打印出来：

二、二分查找树的实现

package tree;

public class BST {
    /**
     * 二分查找树满足以下的特性：
     * 每个节点都比自己左子树上的节点大，并比右子树上的节点小。
     * BST does not allow nodes with the same value
     * <p>
     * O(T):O(logN)
     */

    static class TreeNode {
        public int value;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int value) {
            this.value = value;
        }

        public TreeNode() {

        }
    }

    /**
     * 定义treeNode
     **/
    private TreeNode root;


    /**
     * 跳出循环后，如果是因为current==null而跳出的，则返回null
     * 如果不是，则默认是current跳出的，所以返回的是current
     *
     * @param key 输入的想要查找的值
     * @return 返回null 或者是get到的值value
     */
    public TreeNode get(int key) {
        TreeNode current = root;
        while (current != null && current.value != key) {
            if (key < current.value) {
                current = current.left;
            } else if (key > current.value) {
                current = current.right;
            }
        }
        return current == null ? null : current;
    }


    /**
     * 插入需要两个值
     * 一个父亲节点，一个当前节点
     * <p>
     * void 函数仍然用return的意思是相当于终止函数
     *
     * @param key
     */
    public void insert(int key) {

        // 先判断是否存在，不存在则让输入为root
        if (root == null) {
            root = new TreeNode(key);
            return;
        }

        // current 代表你要插入的值
        // parent 插入的父亲

        TreeNode current = root;
        TreeNode parent = null;
        while (true) {
            parent = current;
            if (key < parent.value) {
                current = parent.left;
                if (current == null) {
                    parent.left = new TreeNode(key);
                    return;
                }
            } else if (key > parent.value) {
                current = parent.right;
                if (current == null) {
                    parent.right = new TreeNode(key);
                    return;
                }
            } else {
                return; // BST does not allow nodes with the same value
            }
        }
    }

    /**
     * 删除需要考虑三种情况
     * <p>
     * Case 1: if node to be deleted has no children （删除节点没有子节点）
     * Case 2: if node to be deleted has only one child （删除节点有一个子节点，可以是左，也可以是右）
     * Case 3: current.left != null && current.right != null （删除节点有两个节点，左右节点都存在）
     *
     * https://www.bilibili.com/video/BV1qQ4y1M7Z4
     *
     * @param key
     * @return
     * @insideparam parent: 用来记录上一个父亲节点
     * @insideparam current：用来记录当前的节点
     */
    public boolean delete(int key) {
        TreeNode parent = root;
        TreeNode current = root;
        boolean isLeftChild = false;
        while (current != null && current.value != key) {
            parent = current;
            if (current.value > key) {
                isLeftChild = true;
                current = current.left;
            } else {
                isLeftChild = false;
                current = current.right;
            }
        }
        if (current == null) {
            return false;
        }
        // Case 1: if node to be deleted has no children
        if (current.left == null && current.right == null) {
            if (current == root) {
                root = null;
            } else if (isLeftChild) {
                parent.left = null;
            } else {
                parent.right = null;
            }
            // Case 2: if node to be deleted has only one child
        } else if (current.right == null) {
            if (current == root) {
                root = current.left;
            } else if (isLeftChild) {
                parent.left = current.left; // 和下方不一致的主要是current.left 和current.right 的区别
            } else {
                parent.right = current.left;
            }
        } else if (current.left == null) {
            if (current == root) {
                root = current.right;
            } else if (isLeftChild) {
                parent.left = current.right;
            } else {
                parent.right = current.right;
            }
            // Case 3: current.left != null && current.right != null
            // 找右子树上的最小的节点来替代--> successor
        } else {
            // 这一步是获得最小的节点
            TreeNode successor = getSuccessor(current);
            if (current == root) {
                root = successor;
            } else if (isLeftChild) {
                parent.left = successor;
            } else {
                parent.right = successor;
            }
            successor.left = current.left;
        }
        return true;
    }

    private TreeNode getSuccessor(TreeNode node) {
        // 找右子树上的最小的节点来替代--> successor
        // 同时遵循保证树形结构的完整
        TreeNode successor = null; // 最后需要放上去的那个节点
        TreeNode successorParent = null;
        TreeNode current = node.right; // 找到待删除位置的sub右子树上找到最小的点
        // 这里的while循环已经保证了最小左子树，但是没法保证最小左子树是否含有右节点
        while (current != null) {
            successorParent = successor;
            successor = current;
            current = current.left;
        }

        // 说明待删除的点是有左子树的
        if (successor != node.right) {
            // 这一步的目的是为了将最小左子树的有节点给连接上
            // 如果没有也就返回null，不影响
            successorParent.left = successor.right;
            successor.right = node.right;
        }
        return successor;
    }

    public static void preOrderTraversal(TreeNode root) {
        if (root == null) {
            return;
        }
        System.out.println(root.value);
        preOrderTraversal(root.left);
        preOrderTraversal(root.right);
    }

}

删除一个节点

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;
        // 接下来处理的是同时有左右两个节点，找到右子树的最小值，也就是右子树的最左边的node
        TreeNode minNode = getMinNode(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;
}

public TreeNode getMinNode(TreeNode node) {
    // BST 左边就是最小的
    while (node.left != null) node = node.left;
    return node;
}

情况 1：A恰好是末端节点，两个子节点都为空，那么它可以当场去世了。

图片来自 LeetCode

if (root.left == null && root.right == null)
    return null;

情况 2：A只有一个非空子节点，那么它要让这个孩子接替自己的位置。

// 排除了情况 1 之后
if (root.left == null) return root.right;
if (root.right == null) return root.left;

情况 3：A有两个子节点，麻烦了，为了不破坏 BST 的性质，A必须找到左子树中最大的那个节点，或者右子树中最小的那个节点来接替自己。我们以第二种方式讲解。

三、遍历树的方法(Tree traversal)

• Pre-order Traversal
  • 先访问节点自己，然后访问左子树，最后再访问右子树
• In-order Traversal
  • 先访问左子树上的节点，再访问自己，最后再访问右子树上的节点
• Post-order Traversal
  • 先访问左右子树，最后再访问自己

注意：以下的实现都是通过recursion来实现的

前序遍历 Preorder Traversal

在前序遍历中，先访问节点自己，然后访问左子树，最后再访问右子树，对于每个节点迭代此操作：

public static void preOrderTraversal(TreeNode root) {
    if(root == null) {
        return;
    }
    System.out.println(root.value);
    preOrderTraversal(root.left);
    preOrderTraversal(root.right);
}

中序遍历 Inorder Traversal

在中序遍历中，先访问左子树上的节点，再访问自己，最后再访问右子树上的节点：

public static void inOrderTraversal(TreeNode root) {
    if(root == null) {
        return;
    }
    inOrderTraversal(root.left);
    System.out.println(root.value);
    inOrderTraversal(root.right);
}

后序遍历 Postorder Traversal

在后序遍历中，先访问左右子树，最后再访问自己：

public static void postOrderTraversal(TreeNode root) {
    if(root == null) {
        return;
    }
    postOrderTraversal(root.left);
    postOrderTraversal(root.right);
    System.out.println(root.value);
}

例子

删除36

四、BST合法性判断

boolean isValidBST(TreeNode root) {
    return isValidBST(root, null, null);
}

/* 限定以 root 为根的子树节点必须满足 max.val > root.val > min.val */
boolean isValidBST(TreeNode root, TreeNode min, TreeNode max) {
    // base case
    if (root == null) return true;
    // 若 root.val 不符合 max 和 min 的限制，说明不是合法 BST
    if (min != null && root.val <= min.val) return false;
    if (max != null && root.val >= max.val) return false;
    // 限定左子树的最大值是 root.val，右子树的最小值是 root.val
    return isValidBST(root.left, min, root) 
        && isValidBST(root.right, root, max);
}

**对于每一个节点root，代码值检查了它的左右孩子节点是否符合左小右大的原则；但是根据 BST 的定义，root的整个左子树都要小于root.val，整个右子树都要大于root.val**。

我们通过使用辅助函数，增加函数参数列表，在参数中携带额外信息，将这种约束传递给子树的所有节点，这也是二叉树算法的一个小技巧吧。

• 需要引入min或者max来记录子树的最大最小值
• 否则会出现如下情况

五、算法题实战

核心框架：

1、如果当前节点会对下面的子节点有整体影响，可以通过辅助函数增长参数列表，借助参数传递信息。

2、在二叉树递归框架之上，扩展出一套 BST 代码框架：

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);
}

3、根据代码框架掌握了 BST 的增删查改操作。

230. Kth Smallest Element in a BST

Given the root of a binary search tree, and an integer k, return the kth (1-indexed) smallest element in the tree.

Example 1:

Input: root = [3,1,4,null,2], k = 1
Output: 1

Example 2:

Input: root = [5,3,6,2,4,null,null,1], k = 3
Output: 3

方法一：递归

算法：

通过构造 BST 的中序遍历序列，则第 k-1 个元素就是第 k 小的元素。

利用arraylist来存储数据，然后返回第k-1个元素

ArrayList<Integer> list = new ArrayList<>();

public int kthSmallest(TreeNode root, int k) {
    list = traverse(root);
    return list.get(k-1);
}

public ArrayList<Integer> traverse(TreeNode root) {
    if (root == null) return null;
    traverse(root.left);
    list.add(root.val);
    traverse(root.right);
    return list;
}

用res 和 rank 来记录元素和结果

int kthSmallest(TreeNode root, int k) {
    // 利用 BST 的中序遍历特性
    traverse(root, k);
    return res;
}

// 记录结果
int res = 0;
// 记录当前元素的排名
int rank = 0;
void traverse(TreeNode root, int k) {
    if (root == null) {
        return;
    }
    traverse(root.left, k);
    /* 中序遍历代码位置 */
    rank++;
    if (k == rank) {
        // 找到第 k 小的元素
        res = root.val;
        return;
    }
    /*****************/
    traverse(root.right, k);
}

时间复杂度 O(N)

没有发挥出BST的潜力，一般的Balanced tree都是O(logN)结果的

538. Convert BST to Greater Tree

难度中等559

Given the root of a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus sum of all keys greater than the original key in BST.

As a reminder, a binary search tree is a tree that satisfies these constraints:

• The left subtree of a node contains only nodes with keys less than the node’s key.
• The right subtree of a node contains only nodes with keys greater than the node’s key.
• Both the left and right subtrees must also be binary search trees.

Note: This question is the same as 1038: https://leetcode.com/problems/binary-search-tree-to-greater-sum-tree/

Example 1:

Input: root = [4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
Output: [30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]

Example 2:

Input: root = [0,null,1]
Output: [1,null,1]

Example 3:

Input: root = [1,0,2]
Output: [3,3,2]

Example 4:

Input: root = [3,2,4,1]
Output: [7,9,4,10]

public TreeNode convertBST(TreeNode root) {
    return traverse(root);
}
int sum = 0;
public TreeNode traverse(TreeNode root){
    if (root == null) return null;
    traverse(root.right);
    sum = sum + root.val;
    root.val = sum;
    traverse(root.left);
    return root;
}