LeetCode145-二叉树中的后序遍历

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/binary-tree-postorder-traversal/

中文链接：https://leetcode-cn.com/problems/binary-tree-postorder-traversal/

题目详述

给定一个二叉树，返回它的 后序 遍历。

示例:

1
2
3
4
5
6
7
8
输入: [1,null,2,3]  
   1
    \
     2
    /
   3 

输出: [3,2,1]

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

题目详解

方法一：递归。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class LeetCode_00145 {

    // 递归
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        postHelper(root, res);
        return res;
    }

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

方法二：迭代。

  • 二叉树的后序遍历的非递归方式不像前序和中序那样容易实现。
  • 二叉树的后序遍历方式是“左右根”。
  • 我们可以对二叉树进行“根右左”遍历，再反转结果序列，就是后序遍历的结果。

以下是这种思路的三种实现。

  1. 运用两个栈。
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
public class LeetCode_00145 {

    // 迭代（运用两个栈）
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        Stack<TreeNode> stack = new Stack<>();
        Stack<Integer> data = new Stack<>();
        stack.push(root);
        while (!stack.empty()) {
            TreeNode p = stack.pop();
            data.push(p.val);
            if (p.left != null) {
                stack.push(p.left);
            }
            if (p.right != null) {
                stack.push(p.right);
            }
        }
        while (!data.isEmpty()) {
            res.add(data.pop());
        }
        return res;
    }
}
  1. 运用一个栈 + 最后 reverse。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class LeetCode_00145 {

    // 迭代（运用一个栈 + 最后 reverse）
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.empty()) {
            TreeNode p = stack.pop();
            res.add(p.val);
            if (p.left != null) {
                stack.push(p.left);
            }
            if (p.right != null) {
                stack.push(p.right);
            }
        }
        Collections.reverse(res);
        return res;
    }
}
  1. 运用一个栈 + 从头添加。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class LeetCode_00145 {

    // 迭代（运用一个栈 + 从头添加）
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.empty()) {
            TreeNode p = stack.pop();
            res.add(0, p.val);
            if (p.left != null) {
                stack.push(p.left);
            }
            if (p.right != null) {
                stack.push(p.right);
            }
        }
        return res;
    }
}