145. Binary Tree Postorder Traversal

https://leetcode.com/problems/binary-tree-postorder-traversal/

iterative

tricky way: like do preorder to do, but the seq of postorder is not correct, but the answer is correct

class Solution {
    // left right root: postorder
    // so do root right left (like preorder) then reverse(add to res first)
    public List<Integer> postorderTraversal(TreeNode root) {
        LinkedList<Integer> res = new LinkedList<>();
        Stack<TreeNode> stack = new Stack<>();
        
        while (root != null || !stack.isEmpty()) {
            if (root != null) {
                stack.push(root);
                res.addFirst(root.val);
                root = root.right;
            } else {
                root = stack.pop().left;
            }   
        }
        return res;
    }
}

recursion

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