- 描述
Given a binary tree, return the postorder traversal of its nodes’ values. For example: Given binary tree
{1, #, 2, 3}, return [2, 3, 1].
Note: Recursive solution is trivial, could you do it iteratively?
回溯思想，有右子树的节点应访问两次，如果节点第一次弹栈，即第一次访问，为该节点打上标记，表示我已经被访问过了，并重新压栈，待遍历完右子树，第二次弹栈，那么就知道此节点左子树和右子树均被访问过，那么此节点可以被加入结果集，应注意节点重新压栈后避免其右子树再次入栈。
时间复杂度O(n)，空间复杂度O(n)
import java.util.*;
public class Solution {
public List<Integer> postorderTraverse(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null)
return result;
Stack<TreeNode> stack = new Stack<>();
TreeNode p = root;
Map<TreeNode, Boolean> map = new HashMap<>();
while (!stack.isEmpty() || p != null) {
if (p != null) {
// 右子树已被压栈一次
if (map.containsKey(p)) {
p = null;
continue;
}
stack.push(p);
if (!map.containsKey(p))
map.put(p, false);
p = p.left;
} else {
p = stack.pop();
// 有右子树的节点弹出且已被访问一次，直接输出
if ((map.get(p) == true && p.right != null) || p.right == null) {
result.add(p.val);
}
// 包含右子树的节点，第一次弹栈后，不输出，而再次入栈，确保右子树访问完，能第二次访问该节点
if (p.right != null && map.containsKey(p) && map.get(p) == false) {
stack.push(p);
map.put(p, true);
}
p = p.right;
}
}
return result;
}
}
