Binary Tree Postorder Traversal -- LeetCode

原題鏈接: http://oj.leetcode.com/problems/binary-tree-postorder-traversal/
跟Binary Tree Inorder Traversal以及Binary Tree Preorder Traversal一樣，二叉樹的後序遍歷我們還是介紹三種方法，第一種是遞歸，第二種是迭代方法，第三種是用線索二叉樹。 遞歸還是那麼簡單，算法的時間復雜度是O(n), 而空間復雜度則是遞歸棧的大小，即O(logn)。代碼如下：

public ArrayList postorderTraversal(TreeNode root) {
    ArrayList res = new ArrayList();
    helper(root, res);
    return res;
}
private void helper(TreeNode root, ArrayList res)
{
    if(root == null)
        return;
    helper(root.left,res);
    helper(root.right,res);
    res.add(root.val);
}

接下來是迭代的做法，本質就是用一個棧來模擬遞歸的過程，但是相比於Binary Tree Inorder Traversal和Binary Tree Preorder Traversal，後序遍歷的情況就復雜多了。我們需要維護當前遍歷的cur指針和前一個遍歷的pre指針來追溯當前的情況（注意這裡是遍歷的指針，並不是真正按後序訪問順序的結點）。具體分為幾種情況：
（1）如果pre的左孩子或者右孩子是cur，那麼說明遍歷在往下走，按訪問順序繼續，即如果有左孩子，則是左孩子進棧，否則如果有右孩子，則是右孩子進棧，如果左右孩子都沒有，則說明該結點是葉子，可以直接訪問並把結點出棧了。
（2）如果反過來，cur的左孩子是pre，則說明已經在回溯往上走了，但是我們知道後序遍歷要左右孩子走完才可以訪問自己，所以這裡如果有右孩子還需要把右孩子進棧，否則說明已經到自己了，可以訪問並且出棧了。
（3）如果cur的右孩子是pre，那麼說明左右孩子都訪問結束了，可以輪到自己了，訪問並且出棧即可。
算法時間復雜度也是O(n)，空間復雜度是棧的大小O(logn)。實現的代碼如下：

public ArrayList postorderTraversal(TreeNode root) {
    ArrayList res = new ArrayList();
    if(root == null)
        return res;
    LinkedList stack = new LinkedList();
    stack.push(root);
    TreeNode pre = null;
    while(!stack.isEmpty())
    {
        TreeNode cur = stack.peek();
        if(pre==null || pre.left==cur || pre.right==cur)
        {
            if(cur.left!=null)
            {
                stack.push(cur.left);
            }
            else if(cur.right!=null)
            {
                stack.push(cur.right);
            }
            else
            {
                res.add(cur.val);
                stack.pop();
            }
        }
        else if(cur.left==pre && cur.right!=null)
        {
            stack.push(cur.right);
        }
        else
        {
            res.add(cur.val);
            stack.pop();
        }
        pre = cur;
    }
    return res;
}

最後介紹Morris遍歷方法，這個方法不需要為每個節點額外分配指針指向其前驅和後繼結點，而是利用葉子節點中的右空指針指向中序遍歷下的後繼節點就可以了，所以優勢在於不需要額外空間。不過同樣相比於Binary Tree Inorder Traversal和Binary Tree Preorder Traversal，後序遍歷的情況要復雜得多，因為後序遍歷中一直要等到孩子結點訪問完才能訪問自己，需要一些技巧來維護。
在這裡，我們需要創建一個臨時的根節點dummy，把它的左孩子設為樹的根root。同時還需要一個subroutine來倒序輸出一條右孩子路徑上的結點。跟迭代法一樣我們需要維護cur指針和pre指針來追溯訪問的結點。具體步驟是重復以下兩步直到結點為空：
1. 如果cur指針的左孩子為空，那麼cur設為其右孩子。
2. 否則，在cur的左子樹中找到中序遍歷下的前驅結點pre（其實就是左子樹的最右結點）。接下來分兩種子情況：
（1）如果pre沒有右孩子，那麼將他的右孩子接到cur。將cur更新為它的左孩子。
（2）如果pre的右孩子已經接到cur上了，說明這已經是回溯訪問了，可以處理訪問右孩子了，倒序輸出cur左孩子到pre這條路徑上的所有結點，並把pre的右孩子重新設為空（結點已經訪問過了，還原現場）。最後將cur更新為cur的右孩子。
空間復雜度同樣是O(1)，而時間復雜度也還是O(n)，倒序輸出的過程只是加大了常數系數，並沒有影響到時間的量級。如果對這個復雜度結果不是很熟悉的朋友，可以先看看Binary Tree Inorder Traversal中的分析，在那個帖子中講得比較詳細。實現的代碼如下：

public ArrayList postorderTraversal(TreeNode root) {
    ArrayList res = new ArrayList();
    TreeNode dummy = new TreeNode(0);
    dummy.left = root;
    TreeNode cur = dummy;
    TreeNode pre = null;
    while(cur!=null)
    {
        if (cur.left==null)
        {
            cur = cur.right;
        }
        else
        {
            pre = cur.left;
            while (pre.right!=null && pre.right!=cur)
                pre = pre.right;
            if (pre.right==null)
            {
                pre.right = cur;
                cur = cur.left;
            }
            else
            {
                reverse(cur.left, pre);
                TreeNode temp = pre;
                while (temp != cur.left)
                {
                    res.add(temp.val);
                    temp = temp.right;
                }
                res.add(temp.val);
                reverse(pre, cur.left);
                pre.right = null;
                cur = cur.right;
            }
        }
    } 
    return res;
}
void reverse(TreeNode start, TreeNode end) 
{
    if (start == end)
        return;
    TreeNode pre = start;
    TreeNode cur = start.right;
    TreeNode next;
    while (pre != end)
    {
        next = cur.right;
        cur.right = pre;
        pre = cur;
        cur = next;
    }
}

到目前為止，二叉樹的三種遍歷的三種方法都介紹過了，後序遍歷相比於前面兩種，還是要復雜一些，個人覺得面試中可能傾向於靠其他兩種遍歷，特別是像Morris遍歷方法，如果沒有准備過很難在面試中寫出這種方法的後序遍歷，主要還是要有概念，就是知道方法的存在性以及優劣的分析就可以了，不過遞歸法和迭代法還是需要掌握一下的。