关于 BST

BST 算是 leetcode 关于树的考察的一个重点了。不过这并不意味着它是一个可以广泛运用的数据结构。主要原因就在于其查找、插入、删除操作的时间复杂度均与树高度成正比，换句话说，就是 O(logn) 。这意味着在很多情况下，时间消耗都比较大。所以我们会转而使用平衡树。比如红黑树，B+，B-等等（不过这些还没学会，就不说了

回到 BST，它有一个重要的特性，就是：

左低右高：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值
左右子树也均为 BST

这也就意味着，它中序遍历的结果是一个递增数列。

另外还有两个关于 BST 的概念。这两个概念是依附于 BST 本身的性质而提出的，并不是独立的概念。

前驱节点(predecessor)：比当前节点小的最大节点
后继节点(successor)：比当前节点大的最小节点

BST 的前驱节点与后继节点

下面有两个不严谨的算法，用来求 BST 中某个节点的 predecessor 和 successor。

predecessor 比当前节点小的最大节点
successor 比当前节点大的最小节点

def predecessor(node):
    node = node.left
    while node.right:
        node = node.right
    return node

def successor(node):
    node = node.right
    while node.left:
        node = node.left
    return node

注意到我们直接取了 node.left 和 node.right 。但该节点的左右子树具体存在与否是不一定的，所以在调用函数前，需要判断左右子树的存在性。

BeforeEach

预先对 BST 的数据类型做一下约定，后不赘述：

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

构建：108 将有序数组转换为二叉搜索树

二叉搜索树的中序遍历是升序数组，这个特性无需赘述了。另外二叉树的中序遍历确实没啥好说的。
不过将一个升序数组转换为平衡二叉搜索树还是很有用的，可以大幅度提高查找、插入、删除的速度。所以就来说一下这道 leetcode 题目。

题目

将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1。

分析

一个数组是中序遍历的结果，意味着如果我们找到了树的根节点，那么就可以根据这个根节点将数组一分为二。左半部分是左子树，右半部分是右子树。
对于一个数列，找一个数字当根节点是没啥限制的。但这道题要求是平衡二叉树。换句话说，我们必须从数列中间选数字，才能保证平衡。
而数列个数可能为奇数或偶数。当为奇数时，存在中位数。当为偶数时，不存在中位数，不过我们可以在中间俩数中随便选一个。
解法不一定是最好的。

代码

def sortedArrayToBST(nums: List[int]) -> TreeNode:
    if not nums: return None

    idx = len(nums) // 2
    mid = nums[idx]

    node = TreeNode(mid)
    node.left = sortedArrayToBST(nums[:idx])
    node.right = sortedArrayToBST(nums[idx+1:])

    return node

注意到 idx = len(nums) // 2 这句代码，是整数除。你也可以选择右边的数字，都一样的。

搜索：700 二叉搜索树中的搜索

名字里就带着搜索，怎么能少了搜索呢？
事实上因为 BST 的~~高低肩~~左低右高的特性，我们在遍历树查找时，并不需要访问到所有的节点，而是根据当前节点的大小关系，找到一条直通目标数的路径即可。
更进一步的说，所花时间与树的高度成正比，即 O(logn)

题目

给定二叉搜索树（BST）的根节点和一个值。你需要在 BST 中找到节点值等于给定值的节点。返回以该节点为根的子树。如果节点不存在，则返回 NULL。

分析

既然是树，那么我们会先从根节点访问。根节点如果存在，且不是目标数的话，它和目标数就会有大小关系。
而 BST 左低右高，所以一个确定下一个访问的节点是左子树还是右子树。
如果访问到叶子节点，或者是不存在的节点了。还没有找到数，那就说明数根本就不存在，纯粹是在累傻小子。

代码

def searchBST(root: TreeNode, val: int) -> TreeNode:
    if not root or root.val == val:
        return root
    return searchBST(root.left, val) if root.val > val else searchBST(root.right, val)

逻辑非常简单，根据 root.val 与 val 的大小关系，选择前进的方向。
当节点不存在，或者找到节点了，那就返回这个子树。
注意访问到不存在的节点不一定是叶子节点。因为左低右高，如果你发现 val 比 root.val 小，但是当前 root 却没有左子树，也就是没有比它更小的节点了，那么也就是找不到了。

插入：701 二叉搜索树中的插入操作

题目

给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。返回插入后二叉搜索树的根节点。输入数据保证，新值和原始二叉搜索树中的任意节点值都不同。
注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。你可以返回任意有效的结果。

分析

注意到插入值与原 BST 中任意节点值都不一样。所以我们一定可以知道当前节点和要插入的值的大小关系。
也就是说，我们通过比较 root.val 和 val 的值，就可以知道应该往左子树走还是右子树走。

代码

def insertIntoBST(root: TreeNode, val: int) -> TreeNode:
    if not root:
        return TreeNode(val)

    if root.val < val:
        root.right = insertIntoBST(root.right, val)
    if root.val > val:
        root.left = insertIntoBST(root.left, val)

    return root

当然了，你可以用迭代来写，但其实一样。

def insertIntoBST(root: TreeNode, val: int) -> TreeNode:
    node = TreeNode(val)
    if not root: return node

    cur = root
    while True:
        if cur.val < val:
            if cur.right:
                cur = cur.right
            else:
                cur.right = node
                break

        if cur.val > val:
            if cur.left:
                cur = cur.left
            else:
                cur.left = node
                break

    return root

迭代就是找了个指针来遍历 BST，其实跟遍历链表是一样的，只不过对于每个节点都有两种可能性。

删除：删除二叉搜索树中的节点

题目

给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。
一般来说，删除节点可分为两个步骤：
首先找到需要删除的节点；
如果找到了，删除它。
说明：要求算法时间复杂度为 O(h)，h 为树的高度。

分析

如何找到要删除的节点？我们在之前讨论 BST 的搜索时就已经完整阐述过了。
删除节点很容易，只要将其变成 None 就行。但问题是，我们需要在删除节点后，还要保证新树依旧是 BST。
从另一个角度来看，BST 的中序遍历是递增数列，也就是说，我们要在递增数列中删除一个值，然后还得保证新数列是递增数列。
那么，我们如何删除一个数组中的数字？按照以下两步：

我们有一个原始数组：
[1, 2, 3, 4, 5]
要删除 3，那么就用 4 覆盖 3：
[1, 2, 4, 4, 5]
删除冗余的 4
[1, 2, 4, 5]

在有序数列中，找到比某一个数大或小的数很容易，但如何在 BST 中找？
答案就是利用 BST 左低右高的性质，寻找其前驱节点与后继节点。

代码

def deleteNode(root: TreeNode, key: int) -> TreeNode:

    def predecessor(node):
        node = node.left
        while node.right:
            node = node.right
        return node.val

    def successor(node):
        node = node.right
        while node.left:
            node = node.left
        return node.val

    if not root: return None
    if root.val > key:
        root.left = deleteNode(root.left, key)
    elif root.val < key:
        root.right = deleteNode(root.right, key)
    else:
        if not root.left and not root.right:
            root = None
        elif root.left:
            root.val = predecessor(root)
            root.left = deleteNode(root.left, root.val)
        elif root.right:
            root.val = successor(root)
            root.right = deleteNode(root.right, root.val)

    return root

主逻辑很简单，分为两层。

第一层：找到要删除的节点
第二层：删除节点
- 第一节：若是叶子节点，直接删除
- 第二节：若不是叶子节点，有左子树，用前驱节点覆盖，然后递归删除前驱节点
- 第三节：若不是叶子节点，有右子树，用后继节点覆盖，然后递归删除后继节点

Space Cowboy

好耶！是 BST