资讯专栏INFORMATION COLUMN

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

ccj659 / 1320人阅读

摘要:解法二迭代中序遍历分析作者二叉搜索树的中序后继是中序遍历中当前节点之后最小的节点。

1. 题目

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

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

1.1 示例

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

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

1.2 说明

1.3 限制

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

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) O(n) ,因为要先遍历所有节点得到中序遍历序列;
  • 控件复杂度: O ( n ) O(n) O(n) ,因此至少需要一个实例属性 _nodes 来保存所有节点。

3. 解法二(迭代中序遍历)

3.1 分析

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

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

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


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

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

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

中序遍历方法的时间复杂度为 O ( h ) O(h) O(h) ,其中 h 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) O(hp) ,其中 O ( h p ) O(h_p) O(hp) 是节点 p 的高度。如果没有右子节点,时间复杂度为 O ( H ) O(H) O(H),其中 h h h 为树的高度;
  • 空间复杂度: 如果节点 p 有右子节点,空间复杂度为 O ( 1 ) O(1) O(1) 。如果没有右子节点,空间复杂度度为 O ( h ) O(h) 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 ) O(1) O(1)

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/124763.html

相关文章

  • LeetCode 叉树专项】把二叉搜索树转换为累加树(538)

    摘要:解法一中序遍历分析由于给定了二叉搜索树,因此首先考虑中序遍历,使用示例,我们先来分别看一下二叉搜索树和累加树中序遍历的结果二叉搜索树二叉累加树。这里还是使用示例,我们再来观察一下二叉搜索树和累加树中序遍历的结果二叉搜索树二叉累加树。 ...

    xcold 评论0 收藏0
  • Leetcode打卡——二叉搜索树(共8题)

    摘要:也就是说,有个节点的平衡二叉搜索树,它的高度是。以搜索操作为例,如果二叉搜索树的高度为,则时间复杂度为。二叉搜索树的高度的确很重要。树集合,中的或者中的,是由高度平衡的二叉搜索树实现的。 ...

    Olivia 评论0 收藏0
  • 树和树的算法

    摘要:树和树的算法一树树的概念树英语是一种抽象数据类型或是实作这种抽象数据类型的数据结构,用来模拟具有树状结构性质的数据集合。一种时间复杂度额外空间复杂度的二叉树的遍历方式,为二叉树的节点个数。 树和树的算法 一、树 1.1 树的概念 树(英语:tree)是一种抽象数据类型(ADT)或是实作这种抽象数据类型的数据结构,用来模拟具有树状结构性质的数据集合。它是由n(n>=1)个有限节点组成一个...

    RaoMeng 评论0 收藏0
  • 树和树的算法

    摘要:树和树的算法一树树的概念树英语是一种抽象数据类型或是实作这种抽象数据类型的数据结构,用来模拟具有树状结构性质的数据集合。一种时间复杂度额外空间复杂度的二叉树的遍历方式,为二叉树的节点个数。 树和树的算法 一、树 1.1 树的概念 树(英语:tree)是一种抽象数据类型(ADT)或是实作这种抽象数据类型的数据结构,用来模拟具有树状结构性质的数据集合。它是由n(n>=1)个有限节点组成一个...

    PiscesYE 评论0 收藏0
  • LeetCode 之 JavaScript 解答第94题 —— 叉树中序遍历

    摘要:小鹿题目二叉树中序遍历给定一个二叉树,返回它的中序遍历。通常递归的方法解决二叉树的遍历最方便不过,但是我还是喜欢增加点难度,用一般的迭代循环来实现。 Time:2019/4/25Title:Binary Tree Inorder TraversalDifficulty: MediumAuthor:小鹿 题目:Binary Tree Inorder Traversal(二叉树中序遍历...

    Jason 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<