Recover Binary Search Tree -- LeetCode

 
這道題是要求恢復一顆有兩個元素調換錯了的二叉查找樹。一開始拿到可能會覺得比較復雜，其實觀察出規律了就比較簡單。主要還是利用二叉查找樹的主要性質，就是中序遍歷是有序的性質。那麼如果其中有元素被調換了，意味著中序遍歷中必然出現違背有序的情況。那麼會出現幾次呢？有兩種情況，如果是中序遍歷相鄰的兩個元素被調換了，很容易想到就只需會出現一次違反情況，只需要把這個兩個節點記錄下來最後調換值就可以；如果是不相鄰的兩個元素被調換了，舉個例子很容易可以發現，會發生兩次逆序的情況，那麼這時候需要調換的元素應該是第一次逆序前面的元素，和第二次逆序後面的元素。比如1234567,1和5調換了，會得到5234167，逆序發生在52和41，我們需要把4和1調過來，那麼就是52的第一個元素，41的第二個元素調換即可。
搞清楚了規律就容易實現了，中序遍歷尋找逆序情況，調換的第一個元素，永遠是第一個逆序的第一個元素，而調換的第二個元素如果只有一次逆序，則是那一次的後一個，如果有兩次逆序則是第二次的後一個。算法只需要一次中序遍歷，所以時間復雜度是O(n)，空間是棧大小O(logn)。代碼如下：

public void recoverTree(TreeNode root) {
    if(root == null)
        return;
    ArrayList pre = new ArrayList();
    pre.add(null);
    ArrayList res = new ArrayList();
    helper(root,pre, res);
    if(res.size()>0)
    {
        int temp = res.get(0).val;
        res.get(0).val = res.get(1).val;
        res.get(1).val = temp;
    }
}
private void helper(TreeNode root, ArrayList pre, ArrayList res)
{
    if(root == null)
    {
        return;
    }
    helper(root.left, pre, res);
    if(pre.get(0)!=null && pre.get(0).val>root.val)
    {
        if(res.size()==0)
        {
            res.add(pre.get(0));
            res.add(root);
        }
        else
        {
            res.set(1,root);
        }
    }
    pre.set(0,root);
    helper(root.right,pre,res);
}

可以看到實現中pre用了一個ArrayList來存，這樣做的原因是因為java都是值傳遞，所以我們要全局變化pre的值（而不是在當前函數裡），只能傳一個數組，才能改變結點的地址，這一點非常重要，也是java和C++一個比較大的區別，不了解的朋友可以研究一下哈。
這道題還是考察二叉樹遍歷，不過應用題目要求套了一個不同的外殼，需要我們利用二叉查找樹的性質觀察出規律之後才能求解。