本文最后更新于:2 个月前

一、二叉搜索树

二叉搜索树(BST)满足的性质:

  • 每个节点中的值必须大于(或等于)存储在其左侧子树中的任何值。
  • 每个节点中的值必须小于(或等于)存储在其右子树中的任何值。

一个二叉搜索树的例子如下所示:

Sample

图1:二叉搜索树举例

因为二叉树的中序遍历会得到一个递增的序列,因此在二叉搜索树里中序遍历比较常用。

给定一个二叉树,我们要判断它是否是二叉搜索树。二叉搜索树的特征比较明显,我们需要判断:(1)当前节点下,其左子树只包含小于当前节点的数;(2)其右子树只包含大于当前节点的数;(3)所有左子树右子树必须也是二叉搜索树。此题是leetcode的第98题,我们用递归、迭代、中序遍历三种方法实现。

注意】直观来看,遍历每个节点,只要当前节点比左节点大比右节点小就行。但这样是不对的,因为我们还要右子树的所有节点都要比当前节点大,左子树的所有节点都要比当前节点小,刚才的做法无法保证这一点。比如下图,虽然根节点5小于右节点6,但右子树有个节点值为4,小于根节点,因此不是二叉搜索树。

Sample

图2:非二叉搜索树举例

这种情况下,在右子树里比较时,要有一个下界,这个子树里的值都不能小于这个下界,这个下界就是根节点的值。同理,根节点的值就是左子树的上界,所有值都不能大于这个上界。

1、递归

# 递归判断是否为二叉搜索树
class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        # 上界初始化为无穷,下界初始化为负无穷
        def helper(node, lower = float('-inf'), upper = float('inf')):
            if not node:
                return True
            
            val = node.val
            # 如果当前节点小于下界或大于上界,则不是BST
            if val <= lower or val >= upper:	
                return False
			# 考察右子树是否有低于下界的
            if not helper(node.right, val, upper):
                return False
            # 考察左子树是否有高于上界的
            if not helper(node.left, lower, val):
                return False
            # 以上都满足,则是BST
            return True

        return helper(root)

复杂度分析:

  • 时间复杂度:$O(N)$,每个节点访问了一次
  • 空间复杂度:$O(N)$,跟进了整个树

2、迭代

# 迭代法,深度优先搜索
class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        if not root:
            return True
        # 初始化栈
        stack = [(root, float('-inf'), float('inf')), ] 
        while stack:
        	# 出栈
            root, lower, upper = stack.pop()
            # 如果not root,说明此节点的父节点没有左孩子或右孩子,continue即可
            if not root:
                continue
                
            val = root.val
            # 判断当前节点
            if val <= lower or val >= upper:
                return False
            # 压栈右孩子
            stack.append((root.right, val, upper))
            # 压栈左孩子
            stack.append((root.left, lower, val))
        return True

复杂度分析:

  • 时间复杂度:$O(N)$,每个节点访问了一次
  • 空间复杂度:$O(N)$,跟进了整个树

3、中序遍历

# 中序遍历
class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        stack, inorder = [], float('-inf')
        
        while stack or root:
        	# 到最左边的叶子节点
            while root:
                stack.append(root)
                root = root.left
            # 出栈
            root = stack.pop()
            # 如果它小于它前一个节点的值,则不是BST(因为是中序遍历,是按照递增排的)
            if root.val <= inorder:
                return False
            # 若它大于前一个值,则将当前值赋值给inorder值
            inorder = root.val
            root = root.right

        return True

复杂度分析:

  • 时间复杂度:时间复杂度 : 最坏情况下(树为二叉搜索树或破坏条件的元素是最右叶结点)为$O(N)$
  • 空间复杂度:$O(N)$用于存储stack

    二、基本操作

    1、在树中搜索某个值

    在搜索二叉树中找到某个值并返回改节点,举例如下图所示。我们要找到值为4的节点,从根节点开始,它大于4,因此在左子树找。左子树的根节点小于4,因此再在其右子树找。此时当前节点值为4,返回该节点。此题对于leetcode的第700题。

Sample

图3:在二叉搜索树中实现搜索操作

递归实现

class Solution:
    def searchBST(self, root: TreeNode, val: int) -> TreeNode:
    	# 如果给节点为空,或该节点值等于要找到的值,则返回改节点
        if not root or root.val == val:
            return root
        # 若改节点值大于val,则在左子树找
        if root.val > val:
            return self.searchBST(root.left,val)
        # 否则在右子树找
        else:
            return self.searchBST(root.right,val)

复杂度分析:

  • 时间复杂度:$O(H)$,其中H是树高。平均时间复杂度:$O(logN)$;最坏时间复杂度:$O(N)$
  • 空间复杂度:$O(H)$,递归栈的深度为H。平均情况下深度为$O(logN)$;最坏情况戏曲深度为$O(N)$

迭代实现

class Solution:
    def searchBST(self, root: TreeNode, val: int) -> TreeNode:
        while root is not None and root.val != val:
            root = root.left if val < root.val else root.right
        return root

复杂度分析:

  • 时间复杂度:$O(H)$,其中H是树高。平均时间复杂度:$O(logN)$;最坏时间复杂度:$O(N)$
  • 空间复杂度:$O(1)$,恒定的额外空间

2、插入操作

在这里实现的二叉搜索树的插入操作,主要思想是为目标节点找出合适的叶节点位置,然后将该节点作为叶节点插入。举例如下图所示:

Sample Sample

图4:在二叉搜索树中实现插入操作

在左边这个树里插入4,从根节点开始,4小于5,因此继续搜索左子树。4大于2,而且2没有右孩子,因此4作为2的右孩子插入到树中。此题对于leetcode的第701题。 **递归实现:**
class Solution:
    def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode:
        if not root:
            return TreeNode(val)
        
        if val > root.val:
            # 在右子树插入
            root.right = self.insertIntoBST(root.right, val)
        else:
            # 在左子树插入
            root.left = self.insertIntoBST(root.left, val)
        return root
复杂度分析: - 时间复杂度:$O(H)$,其中H是树高。平均时间复杂度:$O(logN)$;最坏时间复杂度:$O(N)$ - 空间复杂度:平均情况下 $O(H)$。最坏的情况下是 $O(N)$,是在递归过程中堆栈使用的空间。 **迭代实现:**
class Solution:
    def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode:
        node = root
        while node:
            # 如果val大于当前节点的值,则在右子树插入
            if val > node.val:
                # 如果没有右孩子,则插入
                if not node.right:
                    node.right = TreeNode(val)
                    return root
                else:
                    node = node.right
            # 如果val大于当前节点的值,则在左子树插入
            else:
                # 如果没有左孩子,则插入
                if not node.left:
                    node.left = TreeNode(val)
                    return root
                else:
                    node = node.left
        return TreeNode(val)
复杂度分析: - 时间复杂度:$O(H)$,其中H是树高。平均时间复杂度:$O(logN)$;最坏时间复杂度:$O(N)$。 - 空间复杂度:$O(1)$ ## **3、删除操作** 这里的删除操作是用一个合适的子节点来替换要删除的目标节点,使整体操作变化最小。如果目标节点值大于当前节点,则指向右子树去寻找目标节点;如果目标节点值小于当前节点,则指向左子树去寻找目标节点。如果找到了目标节点,我们分为三种情况: - case1:目标节点没有子节点,可以直接删除目标节点。如下图所示:

Sample

图5:删除操作,情况1

  • case2:目标节点有右节点,则该节点可以由该节点的后继节点(successor,右子树最左边的节点)进行替代,该后继节点位于右子树中较低的位置。然后可以从后继节点的位置递归向下操作以删除后继节点。如下图所示:

    Sample

    图6:删除操作,情况2

  • case3:目标节点只有左节点,可以使用它的前驱节点(predecessor,左子树最右边的节点)进行替代,然后再递归的向下删除前驱节点。如下图所示:

    Sample

    图7:删除操作,情况3

此题对于leetcode的第450题。代码如下:

class Solution:
    def successor(self, root):
        # 最左边的节点
        root = root.right
        while root.left:
            root = root.left
        return root.val
    
    def predecessor(self, root):
        # 最右边的节点
        root = root.left
        while root.right:
            root = root.right
        return root.val
        
    def deleteNode(self, root: TreeNode, key: int) -> TreeNode:
        if not root:
            return None
        
        # 从右子树删除
        if key > root.val:
            root.right = self.deleteNode(root.right, key)
        # 从左子树删除
        elif key < root.val:
            root.left = self.deleteNode(root.left, key)
        # 找到了要删除的节点
        else:
            # case 1
            if not (root.left or root.right):
                root = None
            # case 2
            elif root.right:
                root.val = self.successor(root)
                root.right = self.deleteNode(root.right, root.val)
            # case 3
            else:
                root.val = self.predecessor(root)
                root.left = self.deleteNode(root.left, root.val)
                        
        return root

复杂度分析:

  • 时间复杂度:时间复杂度:${O}(\log N)$。在算法的执行过程中,我们一直在树上向左或向右移动。首先先用$O(H_{1})$的时间找到要删除的节点,$H_{1}$是从根节点到要删除节点的高度。然后删除节点需要 ${O}(H_2)$的时间,$H_{2}$指的是从要删除节点到替换节点的高度。由于 ${O}(H_1 + H_2) = {O}(H)$,$H$ 值得是树的高度,若树是一个平衡树则 $H = \log N$。
  • 空间复杂度:空间复杂度:$O(H)$,递归时堆栈使用的空间,HH 是树的高度

三、例题

二叉搜索树的最近公共祖先

此题为leetcode第235题
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

递归写法:

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        # 递归
        # 当p、q的值都小于root时,要在左子树找
        if p.val < root.val and q.val < root.val:
            return self.lowestCommonAncestor(root.left, p, q)
        # 当p、q的值都大于root时,要在右子树找
        if p.val > root.val and q.val > root.val:
            return self.lowestCommonAncestor(root.right, p, q)
        # 否则p或q分列左右子树,root即为最近公共祖先
        return root

非递归写法:

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        # 非递归
        while root:
            if p.val < root.val and q.val < root.val:
                root = root.left
            elif p.val > root.val and q.val > root.val:
                root = root.right
            else:
                return root