145. Binary Tree Postorder Traversal - Easy

前往題目

想法

• 和inorder與preorder差不多，調換加入的順序

思路

與inorder還有preorder有點區別，比較刁鑽

1. 迭代整個樹
2. 過程中只要當前節點不是null就加入答案，並且放入stack，繼續往右邊節點走
3. 當前節點為null時才去左邊節點
4. 反轉答案並回傳

postorder是先訪問左右子節點再訪問父節點，因此這個思路是反過來操作，所以在最後直接反轉就是答案

Code

網友解答

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList();
        Stack<TreeNode> stack = new Stack();
        TreeNode cur = root;

        while (cur != null || !stack.isEmpty()) {
            // Go to the right child
            if (cur != null) {
                // Add before going to children, that's why reverse at the end
                res.add(cur.val);
                stack.push(cur);
                cur = cur.right;
            } else {
                cur = stack.pop();
                cur = cur.left;
            }
        }

        Collections.reverse(res);

        return res;
    }
}