LeetCode 99：恢復二叉搜索樹——中序遍歷找錯誤節點

題目描述

BST 中兩個節點被錯誤交換，恢復樹結構不變，僅交換節點值。要求 O(1) 空間（Morris 遍歷）或 O(n) 空間均可。

中序遍歷性質

BST 中序遍歷應為嚴格遞增。兩個節點交換會導致序列中出現兩處逆序（相鄰交換則一處）。

O(n) 空間解法：列表記錄

1. 中序遍歷收集節點指針到列表
2. 雙指針從左右向中間掃描，找到第一個 list[i] > list[i+1] 和最後一個 list[j] < list[j-1]
3. 交換兩節點值

Java 實現

public void recoverTree(TreeNode root) {
    List<TreeNode> list = new ArrayList<>();
    inorder(root, list);
    int l = -1, r = -1;
    for (int i = 0; i < list.size()-1; ++i)
        if (list.get(i).val > list.get(i+1).val) { l = i; break; }
    for (int j = list.size()-1; j > 0; --j)
        if (list.get(j).val < list.get(j-1).val) { r = j; break; }
    int tmp = list.get(l).val;
    list.get(l).val = list.get(r).val;
    list.get(r).val = tmp;
}
void inorder(TreeNode n, List<TreeNode> list) {
    if (n == null) return;
    inorder(n.left, list);
    list.add(n);
    inorder(n.right, list);
}

O(1) 空間：Morris 遍歷

利用線索二叉樹思想，無需棧/遞歸，修改右空指針指向後繼，遍歷後恢復。代碼較長，此處略。

複雜度

• 列表法：時間 O(n)，空間 O(n)
• Morris：時間 O(n)，空間 O(1)