leetcode590.N叉树的后序遍历

leetcode590.N叉树的后序遍历

二月 23, 2020

leetcode590. N叉树的后序遍历

给定一个 N 叉树，返回其节点值的后序遍历。

例如，给定一个 3叉树 :
在这里插入图片描述返回其后序遍历: [5,6,3,2,4,1].

说明: 递归法很简单，你可以使用迭代法完成此题吗?

先上递归法，很简单。

1
2
3
4
5
6
7
8
9
10
11
12
13
ArrayList<Integer>list=new ArrayList<>();
    public List<Integer> postorder(Node root) {
        loop(root);
        return list;
    }
    public void loop(Node root){
        if(root!=null){
            for(int i=0;i<root.children.size();i++){
            loop(root.children.get(i));
            }
        list.add(root.val);
        }
    }

迭代法

类似于层序遍历，bfs，把当前节点出栈，把他的子节点全部入栈，但是这么操作完，顺序是反的，所以把弹出来的值在放到一个存储结果的栈里面,这样再弹出来就是正确的顺序。不过这么做会消耗时间。
（看了一下官方题解，我觉得我不知道addFirst和pollLast这两个方法，所以我找了一个替代的方式）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public List<Integer> postorder(Node root) {
    ArrayList<Integer>list=new ArrayList<>();
    if(root==null)return list;
    Stack<Node>stack=new Stack<>();
    Stack<Node>res=new Stack<>();
    stack.push(root);
    //弹出来的顺序是1,4,2,3,6,5
    while(!stack.isEmpty()){
        Node pop=stack.pop();
        res.push(pop);
        for(Node node:pop.children){
            stack.push(node);
        }
    }
    while(!res.isEmpty()){
        Node pop=res.pop();
        list.add(pop.val);
    }
    return list;
}

leetcode 26/100