145. 二叉树的后序遍历

给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。

示例 1：

1
2
输入：root = [1,null,2,3]
输出：[3,2,1]

示例 2：

1
2
输入：root = []
输出：[]

示例 3：

1
2
输入：root = [1]
输出：[1]

提示：

  • 树中节点的数目在范围 [0, 100] 内
  • -100 <= Node.val <= 100

进阶：递归算法很简单，你可以通过迭代算法完成吗

题解：

递归写法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public List<Integer> postorderTraversal(TreeNode root) {
    ArrayList<Integer> result = new ArrayList<>();
    postorder(result,root);
    return result;
}

private void postorder(List<Integer> result,TreeNode root) {
    if (root == null){
        return;
    }
    postorder(result,root.left);
    postorder(result,root.right);
    result.add(root.val);

}

迭代写法：

因为后序遍历的顺序是左右根，所以只要保证出栈顺序为根右左，然后进行一次反转操作即可。

倒推回来，出栈顺序为根右左，所以入栈顺序即为根左右。

至于为什么要把根节点固定操作，因为这样可以保证根节点的访问顺序和操作顺序保持一致，是在前序遍历的基础上做了修改。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();

    if (root == null) {
        return result;
    }

    Stack<TreeNode> stack = new Stack<>();
    //根节点入栈
    stack.push(root);
    //入栈顺序：根--左--右
    //出栈顺序：根--右--左
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();

        result.add(node.val);

        if (node.left != null) {
            stack.push(node.left);
        }

        if (node.right != null) {
            stack.push(node.right);
        }
    }

    //所需结果序列：左--右--根
    Collections.reverse(result);
    return result;

}