99.恢複二叉搜尋樹

題解

前序可以很友善地形成一條搜尋路徑，

中序周遊BST的時候可以得到一個有序序列，

後序可以用來計算一顆算數表達式樹

• 如果前驅節點為空，将其右節點指向目前節點
• 如果前驅節點不為空，說明前驅節點已經指向目前節點，說明我們已經周遊完了目前節點的左子樹，我們必須将前驅節點的右節點置空（隻是利用這個節點暫存資料，起到類似棧的效果），然後通路目前節點的右節點。（x = x.right)

class Solution {
    public void recoverTree(TreeNode root) {
        TreeNode first = null, last = null;
        TreeNode pre = null, cur = root, tail = null;
        while (cur != null) {
            // 模闆代碼，和周遊相同
            tail = cur.left;
            if (tail != null) {
                // 找到 tail 位置
                while (tail.right != null && tail.right != cur) {
                    tail = tail.right;
                }
                if (tail.right == null) {
                    // 暫時連結，充當棧的作用
                    tail.right = cur;
                    cur = cur.left;
                    continue;
                } else {
                    // 斷開連結，保證二叉樹結構不變
                    tail.right = null;
                }
            }
            // 更新 first & last 節點
            if (pre != null && pre.val > cur.val) {
                last = cur;
                if (first == null) {
                    first = pre;
                }
            }
            // 更新 pre & cur 節點
            pre = cur;
            cur = cur.right;
        }
        // 交換
        int temp;
        temp = first.val;
        first.val = last.val;
        last.val = temp;
    }
}