二叉搜索樹第 K 大節點遞歸算法錯誤分析與正確實現

原代碼邏輯缺陷

TreeNode pRoot1 = null;
TreeNode KthNode(TreeNode pRoot, int k) {
    KthNode(pRoot, k, 1);
    return pRoot1;
}
void KthNode(TreeNode pRoot, int k, int count) {
    if (pRoot != null) {
        KthNode(pRoot.left, k, count);  // 1. count 為值傳遞，回溯時不累加
        if (count == k) {               // 2. 中序遍歷位置錯誤
            pRoot1 = pRoot;
            return;
        }
        count++;                        // 3. 遞歸返回後 count 不保留
        KthNode(pRoot.right, k, count);
    }
}

三大核心問題

1. 參數傳遞機制：Java 基本類型值傳遞，遞歸層級間 count 不共享
2. 遍歷順序錯誤：BST 第 K 大需右-根-左逆中序遍歷
3. 早退機制缺失：找到目標後未阻止繼續遞歸

正確遞歸實現

class Solution {
    int count = 0;
    TreeNode result = null;

    TreeNode KthNode(TreeNode root, int k) {
        count = 0;
        result = null;
        reverseInorder(root, k);
        return result;
    }

    void reverseInorder(TreeNode node, int k) {
        if (node == null || result != null) return;
        
        reverseInorder(node.right, k);  // 先遍歷右子樹(較大值)
        
        if (++count == k) {             // 訪問根節點
            result = node;
            return;
        }
        
        reverseInorder(node.left, k);   // 最後遍歷左子樹(較小值)
    }
}

迭代版本（避免棧溢出）

TreeNode KthNodeIter(TreeNode root, int k) {
    Stack stack = new Stack<>();
    TreeNode curr = root;
    int count = 0;
    
    while (curr != null || !stack.isEmpty()) {
        while (curr != null) {
            stack.push(curr);
            curr = curr.right;
        }
        curr = stack.pop();
        if (++count == k) return curr;
        curr = curr.left;
    }
    return null;
}

複雜度分析

• 時間：O(H + k)，H 為樹高
• 空間：O(H) 遞歸棧 / 顯式棧

參考優秀博客：BST 第 K 大節點詳細解析