# leetcode解題：(Easy) 145. Binary Tree Postorder Traversal

題目：[https://leetcode.com/problems/binary-tree-postorder-traversal/](https://leetcode.com/problems/binary-tree-postorder-traversal/)

描述：以後序(postorder)輸出二元樹節點的值

解題思路：遞迴處理二元樹遍歷都很簡單因此採用迭代法。後序相對前序跟中序稍微麻煩一點，直覺地使用先前的方式將node放入stack會產生無法判斷哪些是第一次遇見的父節點還是子節點都已經走訪過的父節點。

leetcode的解法中主流是將原本preoder方法的輸出順序由(父->左->右)改為(父->右->左)，再將結果直接倒過來輸出為(左->右->中)，但這個方法很明顯的只是投機讓輸出正確而已，實際上遍歷方式根本是錯的。

另一種方法則是將已探訪並輸出過的節點刪除，這樣就能讓底下已經沒有子節點的父節點接著輸出，但缺點同樣很明顯：會修改到原本的樹甚至最後根本整顆砍光光，很多情況下根本不適用。

最後則是本篇採用的解題方法：
[https://leetcode.com/problems/binary-tree-postorder-traversal/solutions/45582/a-real-postorder-traversal-without-reverse-or-insert-4ms/](https://leetcode.com/problems/binary-tree-postorder-traversal/solutions/45582/a-real-postorder-traversal-without-reverse-or-insert-4ms/)
方法的邏輯在於stack新增節點時會新增同一個節點2次，當每次pop出一個節點時，如果stack最頂為同樣的節點代表這個節點的子節點還沒走訪完畢，而若stack最頂為不同節點就代表這個節點底下都已經走訪、輸出完畢了，那該節點也能輸出到結果的陣列中了。與前2種方法相比這個方法使用正確的遍歷方式也不會修改到原本的樹，只是stack的空間用量較多(但其實也還是O(n))。

程式碼：

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        if(root == null) return result;

        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.push(root);
        stack.push(root);

        while(!stack.isEmpty()) {
            TreeNode currentNode = stack.pop();
            if(!stack.isEmpty() && stack.peek() == currentNode) {
                if(currentNode.right != null) {
                    stack.push(currentNode.right);
                    stack.push(currentNode.right);
                }
                if(currentNode.left != null) {
                    stack.push(currentNode.left);
                    stack.push(currentNode.left);
                }
            }
            else {
                result.add(currentNode.val);
            }
        }

        return result;
    }
}

時間複雜度：O(n)
空間複雜度：O(n)

###### tags: `leetcode` `easy` `binary tree` `DFS`