145. Binary Tree Postorder Traversal

naive级别递归三连其三：后序遍历。

public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    dfs(root, res);
    return res;
}

public void dfs(TreeNode root, List<Integer> res) {
    if (root == null) return;

    dfs(root.left, res);
    dfs(root.right, res);
    res.add(root.val);
}

递归的理解：写出三个点的后序遍历，然后发现迷之缩进里的两个左右子树的if可以用dfs复用。

public void dfs(TreeNode root, List<Integer> res) {
    if (root == null) return;
        // 左边的坑：dfs(root.left, res);
        if (root.left == null) return;
        res.add(root.left.val);
        // 右边的坑：dfs(root.right, res)
        if (root.right == null) return;
        res.add(root.right.val);
    res.add(root.val);
}

后序遍历的栈：和中序遍历不同的是，虽然后序遍历也有个指针，但是它和前序遍历一样是root节点在栈底，所以root一旦进栈，中间过程就不可能是空。

public List<Integer> postorderTraversal(TreeNode root) {
    LinkedList<Integer> res = new LinkedList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    if (root != null) stack.push(root);
    TreeNode node = root;

    while (!stack.isEmpty()) {
        if (node != null) {
            stack.push(node);
            res.push(node.val);
            node = node.right;
        } else {
            node = stack.pop();
            node = node.left;
        }
    }
    return res;
}

当然也可以和中序遍历一样加在判断条件上

public List<Integer> postorderTraversal(TreeNode root) {
    LinkedList<Integer> res = new LinkedList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode node = root;

    while (!stack.isEmpty() || node != null) {
        if (node != null) {
            stack.push(node);
            res.push(node.val);
            node = node.right;
        } else {
            node = stack.pop();
            node = node.left;
        }
    }
    return res;
}