LeetCode N叉树的前序/后序遍历-一一网

这是我参与更文挑战的第 19 天，活动详情查看：更文挑战

N叉树的前序遍历（589）

题目描述

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

N 叉树在输入中按层序遍历进行序列化表示，每组子节点由空值 null 分隔（请参见示例）。

进阶：

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

示例 1：

输入：root = [1,null,3,2,4,null,5,6]
输出：[1,3,5,6,2,4]
复制代码

示例 2：

输入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
输出：[1,2,3,6,7,11,14,4,8,12,5,9,13,10]
复制代码

提示

N 叉树的高度小于或等于 1000
节点总数在范围 [0, 10^4] 内

思路分析

N 叉树的前序遍历，如果用递归实现也很简单，只需要先将父节点加入目标列表中，然后再从左到右遍历调用preorderInternal。

最后我们也可以用迭代的方法来进行前序遍历链表，其实递归是隐性的为我们建一个栈，所以迭代的话我们可以显示的建立一个栈，前序遍历使用迭代法我们可以先把根节点加入到目标列表中，然后对子节点node.children进行反转，然后在遍历所有的节点加入到栈中，最后继续我们的 while 循环。

代码展示

解法一：时间复杂度是 ${O(n)}$ ，空间复杂度是 ${O(n)}$ 。

    public List<Integer> preorder(Node root) {
        List<Integer> res = new ArrayList<>();
        preorderInternal(root,res);
        return res;
    }

    private void preorderInternal(Node root,List<Integer> res){
        if(root == null){
            return;
        }
        res.add(root.val);
        for(int i = 0;i < root.children.size();++i){
            preorderInternal(root.children.get(i),res);
        }
    }
复制代码

解法二：时间复杂度是 ${O(n)}$ ，空间复杂度是 ${O(n)}$ 。

public List<Integer> preorder(Node root) {
        List<Integer> res = new ArrayList<>();
        if(root == null){
            return res;
        }
        Stack<Node> stack = new Stack<>();
        stack.push(root);
        while(!stack.isEmpty()){
            Node node = stack.pop();
            res.add(node.val);
            Collections.reverse(node.children);
            for(Node n: node.children){
                stack.push(n);
            }

        }
        return res;
    }
复制代码

N叉树的后序遍历（590）

题目描述

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

N 叉树在输入中按层序遍历进行序列化表示，每组子节点由空值 null 分隔（请参见示例）。

进阶：

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

示例 1：

输入：root = [1,null,3,2,4,null,5,6]
输出：[5,6,3,2,4,1]
复制代码

示例 2：

输入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
输出：[2,6,14,11,7,3,12,8,4,13,9,10,5,1]
复制代码

提示

N 叉树的高度小于或等于 1000
节点总数在范围 [0, 10^4] 内

思路分析

N 叉树的后序遍历，如果用递归实现也很简单，只需要从左到右遍历调用postorderInternal，然后再添加我们的根节点。

后序遍历的迭代实现，有些方法也会将最终的列表输出前反转一下，得到真正想要目标列表，但是我们也可以通过直接加到列表头部，不用进行最后的反转。

代码展示

解法一：时间复杂度是 ${O(n)}$ ，空间复杂度是 ${O(n)}$ 。

    public List<Integer> postorder(Node root) {
        List<Integer> res = new ArrayList<>();
        postorderInternal(root,res);
        return res;

    }
    private void postorderInternal(Node root,List<Integer> res){
        if(root == null){
            return;
        }
        for(int i = 0;i < root.children.size();i++){
            postorderInternal(root.children.get(i),res);
        }
        res.add(root.val);
    }
复制代码

解法二：

    public List<Integer> postorder(Node root) {
        List<Integer> res = new ArrayList<>();
        if(root == null){
            return res;
        }
        Stack<Node> stack = new Stack<>();
        stack.push(root);
        while(!stack.isEmpty()){
            Node node = stack.pop();
            res.add(0,node.val);

            for(Node n: node.children){
                stack.push(n);
            }
        }
        return res;
    }
复制代码