145. Binary tree postorder traversal

//145. Binary tree postorder traversal

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

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

        List<Integer> result = new ArrayList<>();

        result.addAll(postorderTraversal(root.left));
        result.addAll(postorderTraversal(root.right));
        result.add(root.val);
        
        return result;


        //Solution 2
        List<Integer> post = new ArrayList<>();

        if(root == null) {
            return post;
        }

        Stack<TreeNode> st1 = new Stack<>();
        Stack<TreeNode> st2 = new Stack<>();

        st1.push(root);

        while(!st1.isEmpty()) {
            root = st1.pop();

            st2.push(root);

            if(root.left != null) {
                st1.push(root.left);
            }

            if(root.right != null) {
                st1.push(root.right);
            }
        }

        while(!st2.isEmpty()) {
            post.add(st2.pop().val);
        }
        
        return post;


        //Solution 3
        List<Integer> post = new ArrayList<>();

        if(root == null) {
            return post;
        }

        Stack<TreeNode> st = new Stack<>();
        TreeNode cur = root;

        while(cur != null || !st.isEmpty()) {
            if(cur != null) {
                st.push(cur);
                cur = cur.left;
            }
            else {
                TreeNode temp = st.peek().right;

                if(temp == null) {
                    temp = st.pop();
                    post.add(temp.val);

                    while(!st.isEmpty() && temp == st.peek().right) {
                        temp = st.pop();
                        post.add(temp.val);
                    }
                }
                else {
                    cur = temp;
                }
            }
        }

        return post;
    }
}