N叉树的前序遍历

题目

N叉树的前序遍历（力扣：589）

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

分析

两种方式实现：

递归：递归非常简单即可实现。优先输出当前节点，然后遍历孩子节点，最后返回结果即可。

迭代：通过栈来辅助实现，先将当前点入栈，当栈不为空时，优先将节点值添加到结果中；然后遍历当前节点的孩子节点，这里需要注意，遍历顺序必须从后往前；遍历完成即可得到结果。

代码实现：方法一

    /*** 589. N叉树的前序遍历*/List<Integer> preList = new ArrayList<>();public List<Integer> preorder(Node root) {if(root == null){return preList;}preList.add(root.val);for(int i=0;i<root.children.size();i++){preorder(root.children.get(i));}return preList;}

代码实现：方法二

    /*** 589. N叉树的前序遍历*/public List<Integer> preorder2(Node root) {List<Integer> preList = new ArrayList<>();if(root == null){return preList;}Stack<Node> stack = new Stack<>();stack.push(root);Node tmp;while (!stack.isEmpty()){tmp = stack.pop();preList.add(tmp.val);for(int i=tmp.children.size()-1;i>=0;i--){stack.push(tmp.children.get(i));}}return preList;}