Uber 樹演算法面試：BST 中第 K 大元素

Uber 面試中的經典樹演算法題。本文通過 BST K 大元素問題，展示中序遍歷的靈活應用和優化技巧，oavoservice 助你掌握樹演算法精髓。

📋 問題定義

給定一棵二元搜尋樹（BST）和整數 k，找到樹中第 k 大的元素。

約束：

• 1 <= k <= BST 節點總數
• 需要優化空間和時間複雜度

🎯 解法演進

方法一：中序遍歷 + 陣列

def kthLargest_v1(root, k):
    def inorder(node):
        if not node:
            return []
        return inorder(node.left) + [node.val] + inorder(node.right)
    
    sorted_vals = inorder(root)
    return sorted_vals[-k]

時間： O(n) 空間： O(n)

方法二：反向中序遍歷（最優）

oavoservice 推薦的優化方法：

def kthLargest_v2(root, k):
    def reverse_inorder(node):
        nonlocal k, result
        if not node or result is not None:
            return
        
        reverse_inorder(node.right)
        
        k -= 1
        if k == 0:
            result = node.val
            return
        
        reverse_inorder(node.left)
    
    result = None
    reverse_inorder(root)
    return result

時間： O(k) 空間： O(h)

方法三：Morris 遍歷（空間 O(1)）

def kthLargest_morris(root, k):
    current = root
    count = 0
    result = None
    
    while current:
        if not current.right:
            count += 1
            if count == k:
                result = current.val
            current = current.left
        else:
            predecessor = current.right
            while predecessor.left and predecessor.left != current:
                predecessor = predecessor.left
            
            if not predecessor.left:
                predecessor.left = current
                current = current.right
            else:
                predecessor.left = None
                count += 1
                if count == k:
                    result = current.val
                current = current.left
    
    return result

時間： O(n) 空間： O(1)

💼 oavoservice 助力

多種解法 - 從基礎到最優 空間優化 - Morris 遍歷技巧 時間優化 - 提前終止遍歷

聯繫 oavoservice，專業樹演算法面試輔助！

標籤： #Uber #BST #樹遍歷 #Morris遍歷 #VO輔助 #面試輔助 #一畝三分地

需要面試真題？ 立刻聯繫微信 Coding0201，獲得真題。