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].
2. Implementation
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null) {
return res;
}
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
TreeNode curNode = null, preNode = null;
while (!stack.isEmpty()) {
curNode = stack.peek();
// Case 1: Traverse down the tree, put left child into stack if it exists, otherwise put right child
if (preNode == null || preNode.left == curNode || preNode.right == curNode) {
if (curNode.left != null) {
stack.push(curNode.left);
}
else if (curNode.right != null) {
stack.push(curNode.right);
}
}
// Case 2: Travese up from left child
else if (curNode.left == preNode) {
if (curNode.right != null) {
stack.push(curNode.right);
}
}
// Case 3: Traverse up from right child
else {
res.add(curNode.val);
stack.pop();
}
preNode = curNode;
}
return res;
}
}