题目
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?
答案
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
Stack<TreeNode> stk = new Stack<>();
Map<TreeNode, Boolean> map = new HashMap<>();
pushLeft(stk, map, root);
while(!stk.isEmpty()) {
TreeNode curr = stk.peek();
Boolean is_right_visited = map.get(curr);
if(is_right_visited) {
list.add(stk.pop().val);
}
else {
if(curr.right != null) {
pushLeft(stk, map, curr.right);
}
map.put(curr, true);
}
}
return list;
}
public void pushLeft(Stack<TreeNode> stk, Map<TreeNode, Boolean> map, TreeNode root) {
while(root != null) {
stk.push(root);
map.put(root, false);
root = root.left;
}
}
}
