Divided each each tree node process into 3 cases (according to the traversal path we drew previously):
2.1. Previous node from current node's parent
2.1.1. if current node has left child, process left subtree.
2.1.2. if current node has no left child but right child, process right subtree. (current child has both left child and right is the case of 2.1.1. <- keep processing the left subtree)
2.1.3. if current has no left or right child (leaf), add the value of current tree node to result set and remove this node from stack, which means this node has been processed.
2.2. Previous node from current node's left child (left subtree has been processed)
2.2.1. if there the current node has right child, process the right subtree.
2.2.2. if no right child, add value of current node into result set and remove it from stack (current node processed).
2.3. Previous node from current node's right child (both left subtree and right subtree has been processed). <- add current node into result set and remove it from stack (current node processed).
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<Integer>();
if (root == null) return result;
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.push(root);
TreeNode prev = null;
while (!stack.empty()) {
TreeNode curr = stack.peek();
//from root or parent
if (prev == null || prev.left == curr || prev.right == curr) {
if (curr.left != null) stack.push(curr.left);
else if (curr.right != null) stack.push(curr.right);
else {
stack.pop();
result.add(curr.val);
}
}
//from the left child
else if (curr.left == prev) {
if (curr.right != null) stack.push(curr.right);
else {
stack.pop();
result.add(curr.val);
}
}
//from the right child
else if (curr.right == prev) {
stack.pop();
result.add(curr.val);
}
prev = curr;
}
return result;
}
