【LeetCode 二叉树专项】二叉搜索树中的中序后继（285）

文章目录

• • 1. 题目
  • • 1.1 示例
    • 1.2 说明
    • 1.3 限制
  • 2. 解法一（递归中序遍历）
  • • 2.1 分析
    • 2.2 实现
    • 2.3 复杂度
  • 3. 解法二（迭代中序遍历）
  • • 3.1 分析
    • 3.2 实现
    • 3.3 复杂度

1. 题目

给定一棵二叉搜索树和其中的一个节点 p ，找到该节点在树中的中序后继。如果节点没有中序后继，请返回 null 。

节点 p 的后继是值比 p.val 大的节点中键值最小的节点。

1.1 示例

• 示例 $1$ ：

• 输入： root = [2,1,3] ， p = 1
• 输出： $2$
• 解释： 这里 $1$ 的中序后继是 $2$ 。请注意 p 和返回值都应是 TreeNode 类型。

• 示例 $2$ ：

• 输入： root = [5, 3, 6, 2, 4, null, null, 1] ， p = 6
• 输出： null
• 解释： 因为给出的节点没有中序后继，所以答案就返回 null 了。

1.2 说明

• 来源： 力扣（LeetCode）
• 链接： https://leetcode-cn.com/problems/inorder-successor-in-bst

1.3 限制

• 树中节点的数目在范围 $[1,10^4]$ 内；
• $-10^5<=\text{Node.val}<=10^5$ ；
• 树中各节点的值均保证唯一。

2. 解法一（递归中序遍历）

2.1 分析

既然要求寻找给定节点的中序遍历后继节点，则自然地可以想到先获得该二叉搜索树的中序遍历序列，然后找并返回给定节点在中序遍历序列中后一个节点即可。

因此，下面的实现先通过一次中序遍历得到二叉搜索树的一个中序遍历序列 self._nodes ，然后在其中找到节点 p 对应的索引，最后根据索引确定是否有后继节点。

2.2 实现

from typing import Optionalclass TreeNode:    def __init__(self, val: int, left=None, right=None):        self.val = val        self.left = left        self.right = rightclass Solution:    def __init__(self):        self._nodes = []    def _inorder(self, root: TreeNode):        if root is None:            return        self._inorder(root.left)        self._nodes.append(root)        self._inorder(root.right)    def initialize(self):        self._nodes = []    def successor(self, root: TreeNode, p: TreeNode) -> Optional[TreeNode]:        self._inorder(root)        index = self._nodes.index(p)        if index >= len(self._nodes) - 1:            return        else:            return self._nodes[index + 1]def main():    node6 = TreeNode(1)    node5 = TreeNode(4)    node4 = TreeNode(2, left=node6)    node3 = TreeNode(6)    node2 = TreeNode(3, left=node4, right=node5)    node1 = TreeNode(5, left=node2, right=node3)    root = node1    sln = Solution()    def print_successor(suc: TreeNode):        if suc:            print(suc.val)        else:            print(None)    print_successor(sln.successor(root, node6))  # 2    sln.initialize()    print_successor(sln.successor(root, node2))  # 4    sln.initialize()    print_successor(sln.successor(root, node5))  # 5    sln.initialize()    print_successor(sln.successor(root, node3))  # Noneif __name__ == "__main__":    main()

细心的读者可能已经发现了，在上述实现的测试代码中，每调用一次寻找后继节点的 successor() 方法之后，都调用了一次 initialize() 方法将对象的实例属性 _nodes 清空，原因在于每次调用 successor() 时，该方法都会调用一次 _inorder() 方法，如果不这么做会导致 _nodes 实例属性包含多组中序遍历序列，从而产生意料之外的错误。

实际上，稍显优雅的做法如下，即将调用 _inorder() 方法获得给定二叉搜索树中序序列的操作放在初始化方法 __init__() 中，而在 successor() 方法中仅保留获取后继节点的逻辑，这样就不会导致 _nodes 实例属性在 ElegantSolution 对象的生命周期内被追加多组中序遍历序列了。

from typing import Optionalclass TreeNode:    def __init__(self, val: int, left=None, right=None):        self.val = val        self.left = left        self.right = rightclass ElegantSolution:    def __init__(self, root: TreeNode):        self._nodes = []        self._inorder(root)    def _inorder(self, root: TreeNode):        if root is None:            return        self._inorder(root.left)        self._nodes.append(root)        self._inorder(root.right)    def successor(self, p: TreeNode) -> Optional[TreeNode]:        index = self._nodes.index(p)        if index >= len(self._nodes) - 1:            return        else:            return self._nodes[index + 1]def print_successor(suc: TreeNode):    if suc:        print(suc.val)    else:        print(None)def main():    node6 = TreeNode(1)    node5 = TreeNode(4)    node4 = TreeNode(2, left=node6)    node3 = TreeNode(6)    node2 = TreeNode(3, left=node4, right=node5)    node1 = TreeNode(5, left=node2, right=node3)    root = node1    sln = ElegantSolution(root)    print_successor(sln.successor(node6))  # 2    print_successor(sln.successor(node2))  # 4    print_successor(sln.successor(node5))  # 5    print_successor(sln.successor(node3))  # Noneif __name__ == "__main__":    main()

2.3 复杂度

• 时间复杂度： $O(n)$ ，因为要先遍历所有节点得到中序遍历序列；
• 控件复杂度： $O(n)$ ，因此至少需要一个实例属性 _nodes 来保存所有节点。

3. 解法二（迭代中序遍历）

3.1 分析

• 作者： LeetCode

二叉搜索树的中序后继是中序遍历中当前节点之后 val 最小的节点。

可以分成两种情况来讨论：

• 如果当前节点有右子节点的话，中序后继在当前节点之下，如下图中红色节点所示；
• 如果当前节点没有右子节点的话，中序后继在当前节点之上，如下图中蓝色节点所示。

如果是下图这种情况，即当前节点有右子节点，找到顺序后继很简单，先找到当前节点的右孩子，然后再持续往左直到左孩子为空。

下面再来看一个复杂一点的情况，即当前节点无右子节点，这时候由于无法访问父亲节点，只能从根节点开始中序遍历。中序遍历通常由有递归和迭代的实现方式，这里用迭代的实现方式会更好一点。

直接在中序遍历过程保存前一个访问的节点，判断前一个节点是否为 p，如果是的话当前节点就是 p 节点的顺序后继。

中序遍历方法的时间复杂度为 $O(h)$ ，其中 $h$ 为树的高度。在第一种情况下也可以用中序遍历的方法，但之前的方法更快一点。

3.2 实现

from typing import Optionalclass TreeNode:    def __init__(self, val: int, left=None, right=None):        self.val = val        self.left = left        self.right = rightclass Solution:    def inorder_successor(self, root: TreeNode, p: TreeNode) -> Optional[TreeNode]:        if root is None or not isinstance(root, TreeNode):            return        if p.right:            node = p.right            while node.left:                node = node.left            return node        stack, prev = [], float("-inf")        cursor = root        while True:            if cursor:                stack.append(cursor)                cursor = cursor.left            elif stack:                node = stack.pop()                if prev == p.val:                    return node                prev = node.val                cursor = node.right            else:                break        returndef print_successor(suc: TreeNode):    if suc:        print(suc.val)    else:        print(None)def main():    node6 = TreeNode(1)    node5 = TreeNode(4)    node4 = TreeNode(2, left=node6)    node3 = TreeNode(6)    node2 = TreeNode(3, left=node4, right=node5)    node1 = TreeNode(5, left=node2, right=node3)    root = node1    sln = Solution()    print_successor(sln.inorder_successor(root, node6))  # 2    print_successor(sln.inorder_successor(root, node2))  # 4    print_successor(sln.inorder_successor(root, node5))  # 5    print_successor(sln.inorder_successor(root, node3))  # Noneif __name__ == "__main__":    main()

3.3 复杂度

• 时间复杂度： 如果节点 p 有右子节点，时间复杂度为 $O(h_p)$ ，其中 $O(h_p)$ 是节点 p 的高度。如果没有右子节点，时间复杂度为 $O(H)$，其中 $h$ 为树的高度；
• 空间复杂度： 如果节点 p 有右子节点，空间复杂度为 $O(1)$ 。如果没有右子节点，空间复杂度度为 $O(h)$ 。

实际上，上述迭代解法并没有充分利用给定的是一棵二叉搜索树这一个条件，如果利用这个条件，上述的迭代实现可以进一步优化如下：

from typing import Optionalclass TreeNode:    def __init__(self, val: int, left=None, right=None):        self.val = val        self.left = left        self.right = rightclass Solution:    def inorder_successor(self, root: TreeNode, p: TreeNode) -> Optional[TreeNode]:        if root is None or not isinstance(root, TreeNode):            return        if p.right:            node = p.right            while node.left:                node = node.left            return node        successor = None        while root:            if root.val < p.val:                root = root.right            elif root.val > p.val:                successor = root                root = root.left            else:                break        return successor

上述实现进一步将空间复杂度降低到了 $O(1)$ 。