Simple JAVA solution by reversing root, right, left sequence

  • 1

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


    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'
        			root = root.right;
        		root = stack.pop();// Backtrack to higher level node A
        		root = root.left; // Switch to left branch
        	return res;

Log in to reply

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