文章目錄

• • 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,\text{?}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)$ 。