145. Binary Tree Postorder Traversal

Version #2  Stack Double Push [TODO]

Version #1 Stack -> push right-root reversely

1.1 Create an empty stack2.1 Do following while root is not NULL    a) Push root's right child and then root to stack.    b) Set root as root's left child.2.2 Pop an item from stack and set it as root.    a) If the popped item has a right child and the right child        is at top of stack, then remove the right child from stack,       push the root back and set root as root's right child.    b) Else print root's data and set root as NULL.2.3 Repeat steps 2.1 and 2.2 while stack is not empty.

The tricky part is we can't determine if the current node is fully checked or not
We can only add it to result if both its left and right children are fully checked -> that's why we might have a double push method
So here we firstly push right and then push curr -> and then fully check curr.left
When we come back to curr node, there are 2 situations 1.It comes back from its left child 2.It comes back from its right child
Now if we check stack.peek() == curr.right we know that it is from the left child
    So! We should step into its right subtree to check, right?
    How? Somehow we want to come back after the right subtree check is fully done.
    So we firstly pop right out -> stack.pop()
    And then we push our curr back
    and then we go to curr.right
If stack.peek() != curr.right -> This is the second time we visit curr!
    now we need to add curr.val to result
    Important part is! Remember to SET CURR  = NULL -> so in the next round it will pop from stack

69.78 %
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
Deque<TreeNode> deque = new ArrayDeque<>();
TreeNode curr = root;
while (curr != null || !deque.isEmpty()) {
while (curr != null) {
if (curr.right != null) {
deque.addFirst(curr.right);
}
deque.addFirst(curr);
curr = curr.left;
}
curr = deque.removeFirst();
// curr.right can be null
if (!deque.isEmpty() && curr.right == deque.peekFirst()) {
deque.removeFirst();
deque.addFirst(curr);
curr = curr.right;
} else {
result.add(curr.val); // curr.right has been visited
curr = null;
}
}
return result;
    }
}