# Simple JAVA solution by reversing root, right, left sequence

• Solution. Non-Recursive: Stack. time = O(n) - each node is visited once; space = O(n)

Explanation

Postorder: left, right, root
Preorder : root, right, left

Postorder is actually reverse order of Preorder. (Just travel to tree's right leaf at first, instead of left leaf).
The basic idea is to use stack to simulate the recursion procedure: for each node, travel to its right child until it's right leaf, then pop to right leaf's higher level node A, and switch to A's left branch. Keep the above steps until cur is null and stack is empty.

Trick: Add value to array's first position to reverse the order.

``````    public ArrayList<Integer> postorderTraversal(TreeNode root) {
ArrayList<Integer> res = new ArrayList<Integer>();
if (root == null) return res;

Stack<TreeNode> stack = new Stack<TreeNode>();
while (root != null || !stack.isEmpty()) {// Traversal order: root right left
while (root != null) {// Travel to each node's right child, till reach the right leaf
res.add(0, root.val);// Insert val at first of res array: reverse order from 'root right left' to 'left right root'
stack.push(root);
root = root.right;
}
root = stack.pop();// Backtrack to higher level node A
root = root.left; // Switch to left branch
}
return res;
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.