145. 二叉树的后序遍历

题目描述
​原题​
给定一个二叉树，返回它的 后序 遍历。
示例:
1
输入: [1,null,2,3]  
2
   1
3
    \
4
     2
5
    /
6
   3 
7
​
8
输出: [3,2,1]
Copied!
进阶: 递归算法很简单，你可以通过迭代算法完成吗？
题解
递归
1
class Solution {
2
    public List<Integer> postorderTraversal(TreeNode root) {
3
        List<Integer> list = new ArrayList<>();
4
        if(root != null){
5
            list.addAll(postorderTraversal(root.left));
6
            list.addAll(postorderTraversal(root.right));
7
            list.add(root.val);
8
        }
9
        return list;
10
    }
11
}
Copied!
迭代
1
class Solution {
2
    public List<Integer> postorderTraversal(TreeNode root) {
3
        LinkedList<Integer> list = new LinkedList<>();
4
        if(root == null){
5
            return list;
6
        }
7
        LinkedList<TreeNode> stack = new Stack<>();
8
        stack.push(root);
9
        while(!stack.isEmpty()){
10
            //后序遍历 left right root
11
            //root right left
12
            TreeNode node = stack.pop();
13
            list.addFirst(node.val);
14
            if(node.left!=null){
15
                stack.push(node.left);
16
            }
17
            if(node.right!=null){
18
                stack.push(node.right);
19
            }
20
        }
21
        return list;
22
    }
23
}
Copied!

以前

94. 二叉树的中序遍历

下一个

589. N叉树的前序遍历

最近更新 6mo ago

复制链接

内容