文章目錄

• • 1. 題目
  • • 1.1 示例
    • 1.2 說明
    • 1.3 限制
  • 2. 解法一（遞歸中序遍歷）
  • • 2.1 分析
    • 2.2 實(shí)現(xiàn)
    • 2.3 復(fù)雜度
  • 3. 解法二（迭代中序遍歷）
  • • 3.1 分析
    • 3.2 實(shí)現(xiàn)
    • 3.3 復(fù)雜度

1. 題目

給定一棵二叉搜索樹和其中的一個(gè)節(jié)點(diǎn) p ，找到該節(jié)點(diǎn)在樹中的中序后繼。如果節(jié)點(diǎn)沒有中序后繼，請(qǐng)返回 null 。

節(jié)點(diǎn) p 的后繼是值比 p.val 大的節(jié)點(diǎn)中鍵值最小的節(jié)點(diǎn)。

1.1 示例

• 示例 $1$ ：

• 輸入： root = [2,1,3] ， p = 1
• 輸出： $2$
• 解釋： 這里 $1$ 的中序后繼是 $2$ 。請(qǐng)注意 p 和返回值都應(yīng)是 TreeNode 類型。

• 示例 $2$ ：

• 輸入： root = [5, 3, 6, 2, 4, null, null, 1] ， p = 6
• 輸出： null
• 解釋： 因?yàn)榻o出的節(jié)點(diǎn)沒有中序后繼，所以答案就返回 null 了。

1.2 說明

• 來(lái)源： 力扣（LeetCode）
• 鏈接： https://leetcode-cn.com/problems/inorder-successor-in-bst

1.3 限制

• 樹中節(jié)點(diǎn)的數(shù)目在范圍 $[1,\text{?}10^4]$ 內(nèi)；
• $?10^5<=\text{Node.val}<=10^5$ ；
• 樹中各節(jié)點(diǎn)的值均保證唯一。

2. 解法一（遞歸中序遍歷）

2.1 分析

既然要求尋找給定節(jié)點(diǎn)的中序遍歷后繼節(jié)點(diǎn)，則自然地可以想到先獲得該二叉搜索樹的中序遍歷序列，然后找并返回給定節(jié)點(diǎn)在中序遍歷序列中后一個(gè)節(jié)點(diǎn)即可。

因此，下面的實(shí)現(xiàn)先通過一次中序遍歷得到二叉搜索樹的一個(gè)中序遍歷序列 self._nodes ，然后在其中找到節(jié)點(diǎn) p 對(duì)應(yīng)的索引，最后根據(jù)索引確定是否有后繼節(jié)點(diǎn)。

2.2 實(shí)現(xiàn)

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()

細(xì)心的讀者可能已經(jīng)發(fā)現(xiàn)了，在上述實(shí)現(xiàn)的測(cè)試代碼中，每調(diào)用一次尋找后繼節(jié)點(diǎn)的 successor() 方法之后，都調(diào)用了一次 initialize() 方法將對(duì)象的實(shí)例屬性 _nodes 清空，原因在于每次調(diào)用 successor() 時(shí)，該方法都會(huì)調(diào)用一次 _inorder() 方法，如果不這么做會(huì)導(dǎo)致 _nodes 實(shí)例屬性包含多組中序遍歷序列，從而產(chǎn)生意料之外的錯(cuò)誤。

實(shí)際上，稍顯優(yōu)雅的做法如下，即將調(diào)用 _inorder() 方法獲得給定二叉搜索樹中序序列的操作放在初始化方法 __init__() 中，而在 successor() 方法中僅保留獲取后繼節(jié)點(diǎn)的邏輯，這樣就不會(huì)導(dǎo)致 _nodes 實(shí)例屬性在 ElegantSolution 對(duì)象的生命周期內(nèi)被追加多組中序遍歷序列了。

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 復(fù)雜度

• 時(shí)間復(fù)雜度： $O(n)$ ，因?yàn)橐缺闅v所有節(jié)點(diǎn)得到中序遍歷序列；
• 控件復(fù)雜度： $O(n)$ ，因此至少需要一個(gè)實(shí)例屬性 _nodes 來(lái)保存所有節(jié)點(diǎn)。

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

3.1 分析

• 作者： LeetCode

二叉搜索樹的中序后繼是中序遍歷中當(dāng)前節(jié)點(diǎn)之后 val 最小的節(jié)點(diǎn)。

可以分成兩種情況來(lái)討論：

• 如果當(dāng)前節(jié)點(diǎn)有右子節(jié)點(diǎn)的話，中序后繼在當(dāng)前節(jié)點(diǎn)之下，如下圖中紅色節(jié)點(diǎn)所示；
• 如果當(dāng)前節(jié)點(diǎn)沒有右子節(jié)點(diǎn)的話，中序后繼在當(dāng)前節(jié)點(diǎn)之上，如下圖中藍(lán)色節(jié)點(diǎn)所示。

如果是下圖這種情況，即當(dāng)前節(jié)點(diǎn)有右子節(jié)點(diǎn)，找到順序后繼很簡(jiǎn)單，先找到當(dāng)前節(jié)點(diǎn)的右孩子，然后再持續(xù)往左直到左孩子為空。

下面再來(lái)看一個(gè)復(fù)雜一點(diǎn)的情況，即當(dāng)前節(jié)點(diǎn)無(wú)右子節(jié)點(diǎn)，這時(shí)候由于無(wú)法訪問父親節(jié)點(diǎn)，只能從根節(jié)點(diǎn)開始中序遍歷。中序遍歷通常由有遞歸和迭代的實(shí)現(xiàn)方式，這里用迭代的實(shí)現(xiàn)方式會(huì)更好一點(diǎn)。

直接在中序遍歷過程保存前一個(gè)訪問的節(jié)點(diǎn)，判斷前一個(gè)節(jié)點(diǎn)是否為 p，如果是的話當(dāng)前節(jié)點(diǎn)就是 p 節(jié)點(diǎn)的順序后繼。

中序遍歷方法的時(shí)間復(fù)雜度為 $O(h)$ ，其中 $h$ 為樹的高度。在第一種情況下也可以用中序遍歷的方法，但之前的方法更快一點(diǎn)。

3.2 實(shí)現(xiàn)

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 復(fù)雜度

• 時(shí)間復(fù)雜度： 如果節(jié)點(diǎn) p 有右子節(jié)點(diǎn)，時(shí)間復(fù)雜度為 $O(h_p)$ ，其中 $O(h_p)$ 是節(jié)點(diǎn) p 的高度。如果沒有右子節(jié)點(diǎn)，時(shí)間復(fù)雜度為 $O(H)$，其中 $h$ 為樹的高度；
• 空間復(fù)雜度： 如果節(jié)點(diǎn) p 有右子節(jié)點(diǎn)，空間復(fù)雜度為 $O(1)$ 。如果沒有右子節(jié)點(diǎn)，空間復(fù)雜度度為 $O(h)$ 。

實(shí)際上，上述迭代解法并沒有充分利用給定的是一棵二叉搜索樹這一個(gè)條件，如果利用這個(gè)條件，上述的迭代實(shí)現(xiàn)可以進(jìn)一步優(yōu)化如下：

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

上述實(shí)現(xiàn)進(jìn)一步將空間復(fù)雜度降低到了 $O(1)$ 。