【每日一题-leetcode】590.N叉数的后序遍历

590.N叉数的后序遍历

590. N叉树的后序遍历

难度简单58

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

例如，给定一个 3叉树 :

返回其后序遍历: [5,6,3,2,4,1].

1.递归

时间复杂度:O(n)

空间复杂度:O(n)

  LinkedList<Integer> linkedList = new LinkedList();
        //1.一个LikedList链表存储数值
        //2.递归调用
        // a.如果根节点为null 返回
        // b.依次遍历根节点的孩子节点 
        public List<Integer> postorder(Node root) {
            recur(root);
            return linkedList;
        }
    
        public void recur(Node root){
            if(root == null) return;
            for(Node node : root.children){
                recur(node);
            }
            linkedList.add(root.val);
        }

2.栈迭代

时间复杂度:O(n)

空间复杂度:O(n)

// 1.N叉树的后序遍历 左右根 
// 2.用一个链表存储数据 每次添加首节点 依次往后移动
// 3.将root节点push到栈中 遍历左右子节点。如果不为null 继续
public List<Integer> postorder(Node root) {
    if(root == null) return new ArrayList();
    LinkedList<Integer> linkedList = new LinkedList();
    Stack<Node> stack = new Stack();
    stack.push(root);
    while(!stack.isEmpty()){
        root = stack.pop();
        linkedList.offerFirst(root.val);//先进排在最后
        for(Node node : root.children){
            stack.push(node);
        }
    }
    return linkedList;
}