Examples: 1 / \ 2 3 ==> 4526731 / \ / \ 4 5 6 7
Stack
for traversing through the nodes
at each level and add the nodes to the ArrayList in left-right-root
order.
1. Create a Stack
object to store tree nodes
.
2. Push the root node onto the Stack
.
3. Start a loop for traversing through the nodes, with the condition that stack is not empty
.
4. Traverse down the tree and check if current node is a leaf
, process it and pop the stack
else continue down the tree.
5. Traverse up the tree from the left node and check if there is a right child, if yes, push it to stack
else, process parent and pop stack.
6. Traverse up the tree from the right node and process parent node and pop Stack
.
public ArrayList<Integer> postorderItr(TreeNode root) { }
C
Java
Python