Question

Formatted question description: https://leetcode.ca/all/145.html

145	Binary Tree Postorder Traversal

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

For example:
Given binary tree {1,#,2,3},
   1
    \
     2
    /
   3
return [3,2,1].

Note: Recursive solution is trivial, could you do it iteratively?

@tag-tree

Algorithm

Since the order of post-order traversal is left-right-root, and the order of pre-order traversal is root-left-right, the two are actually very similar.

You can make some small changes in the method of pre-order traversal to make it work. The order becomes root-right-left, and then flipped, that is, left-right-root. The flip method is to add the result res in the reverse direction.

Each time, when adding to stack, left and then right, so that when the stack is processed, it is right and then left.

Code

Java

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class Binary_Tree_Postorder_Traversal {

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    public class Solution_two_stacks {
        public List<Integer> postorderTraversal(TreeNode root) {

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

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

            Stack<TreeNode> sk = new Stack<>();
            Stack<TreeNode> reversedResult = new Stack<>();
            sk.push(root);

            while (!sk.isEmpty()) {
                TreeNode current = sk.pop();

                reversedResult.push(current);

                // @note:@memorize: left first then right. why? - right will be popped out first
                if (current.left != null) {
                    sk.push(current.left);
                }
                if (current.right != null) {
                    sk.push(current.right);
                }

            }

            // reversed to natural order
            while (!reversedResult.isEmpty()) {
                list.add(reversedResult.pop().val); // append to head of list
            }

            return list;

        }
    }

	public class Solution {
	    public List<Integer> postorderTraversal(TreeNode root) {

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

            // Check for empty tree
            if (root == null) {
                return list;
            }

            Stack<TreeNode> sk = new Stack<TreeNode>();
            sk.push(root);
            TreeNode prev = null;

            while (!sk.isEmpty()) {
                TreeNode current = sk.peek();

                /*
                 * go down the tree in search of a leaf if so process it and
                 * pop stack otherwise move down
                 */
                if (prev == null || prev.left == current || prev.right == current) {
                    if (current.left != null) {
                        sk.push(current.left);
                    } else if (current.right != null) {
                        sk.push(current.right);
                    } else { // left node here
                        sk.pop();
                        list.add(current.val);
                    }

                /*
                 * go up the tree from left node, if the child is right push
                 * it onto stack otherwise process parent and pop stack
                 */
                } else if (current.left == prev) {
                    if (current.right != null) {
                        sk.push(current.right);
                    } else {
                        sk.pop();
                        list.add(current.val);
                    }

                /*
                 * go up the tree from right node and after coming back from
                 * right node process parent and pop stack
                 */
                } else if (current.right == prev) {
                    sk.pop();
                    list.add(current.val);
                }

                prev = current;
            }

            return list;

	    }
	}

}

All Problems

All Solutions