Binary Tree Postorder Traversal

Given a binary tree, return the postorder traversal of its nodes' values.

Have you met this question in a real interview? 

Yes

Example

Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [3,2,1].

Challenge

Can you do it without recursion?

/**

 * Definition of TreeNode:

 * public class TreeNode {

 *     public int val;

 *     public TreeNode left, right;

 *     public TreeNode(int val) {

 *         this.val = val;

 *         this.left = this.right = null;

 *     }

 * }

 */

public class Solution {

    /**

     * @param root: The root of binary tree.

     * @return: Postorder in ArrayList which contains node values.

     */

    public ArrayList<Integer> postorderTraversal(TreeNode root) {

        // write your code here

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

        Stack<TreeNode> stack = new Stack<TreeNode>();

        if(root != null)

        stack.push(root);

        while(!stack.isEmpty()){

           root = stack.pop();

           result.add(root.val);

           if(root.left != null) stack.push(root.left);

           if(root.right != null) stack.push(root.right);

        }

        Collections.reverse(result);

        return result;

    }

}

recursion:

/**

 * Definition of TreeNode:

 * public class TreeNode {

 *     public int val;

 *     public TreeNode left, right;

 *     public TreeNode(int val) {

 *         this.val = val;

 *         this.left = this.right = null;

 *     }

 * }

 */

public class Solution {

    /**

     * @param root: The root of binary tree.

     * @return: Postorder in ArrayList which contains node values.

     */

    public ArrayList<Integer> postorderTraversal(TreeNode root) {

        // write your code here

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

        recursion(root, result);

        return result;

    }

    

    private void recursion(TreeNode root, ArrayList<Integer> result){

        if(root == null) return;

        recursion(root.left, result);

        recursion(root.right, result);

        result.add(root.val);

    }

}