[LeetCode] 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?

Thought process:

Postorder traversal visits a tree in the order of left subtree - right subtree - root.

Solution 1 (Recursive):

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public List<Integer> postorderTraversal(TreeNode root) { List<Integer> postorder = new ArrayList<>(); postorderTraversal(root, postorder); return postorder; } private void postorderTraversal(TreeNode root, List<Integer> postorder) { if (root == null) { return; } postorderTraversal(root.left, postorder); postorderTraversal(root.right, postorder); postorder.add(root.val); } }

Time complexity: O(n).

The recursive solution is trivial. To solve this iteratively, we need to use a stack to simulate the function call stack. 

The iterative postorder traversal is not as straightforward as preorder. In preorder traversal, we can simply add a node to the result list in the while loop. But for postorder traversal, a node should be added after all of its descendants are visited. This makes it hard to determine when can we pop a node off the stack. I came up with two ways to do this, both are not ideal:

1. Keep a set of visited nodes. When we check a node at the top of stack, check if both of its children are visited. If so, pop it off the stack and add it to list. This method requires extra space.
2. Modify the tree as we traverse it. After a node is visited, remove it from the tree. Later when we check a node, if both of its children are null, add it to list.

The optimal solution of this problem is to visit nodes according to the reverse order of postorder traversal, which is root - right subtree - left subtree, and reverse the list afterwards. This solves the problem of not knowing when to add a node to list.

Solution 2 (Iterative):

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public List<Integer> postorderTraversal(TreeNode root) { List<Integer> postorder = new ArrayList<>(); Stack<TreeNode> stack = new Stack<>(); stack.push(root); while (!stack.isEmpty()) { TreeNode node = stack.pop(); if (node == null) { continue; } postorder.add(node.val); stack.push(node.left); stack.push(node.right); } Collections.reverse(postorder); return postorder; } }

Time complexity: O(n).

Solution 3 (Postorder iterator):

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { class PostorderIterator implements Iterator<Integer> { private Stack<TreeNode> stack; private Set<TreeNode> visited; public PostorderIterator(TreeNode root) { stack = new Stack<>(); visited = new HashSet<>(); if (root != null) { stack.push(root); } } @Override public boolean hasNext() { return !stack.isEmpty(); } @Override public Integer next() { while (!visited.contains(stack.peek())) { TreeNode node = stack.peek(); visited.add(node); if (node.right != null) { stack.push(node.right); } if (node.left != null) { stack.push(node.left); } } return stack.pop().val; } } public List<Integer> postorderTraversal(TreeNode root) { List<Integer> traversal = new ArrayList<>(); PostorderIterator it = new PostorderIterator(root); while (it.hasNext()) { traversal.add(it.next()); } return traversal; } }

Time complexity:

1. hasNext(): O(1).
2. next(): in the worst case, the tree is a line. O(n). On the average case, next() will be called n times and at most n nodes will be pushed onto stack. So O(1) on average.
3. postorderTraversal: O(n).