題目

方法一：單循環(huán)棧做法

關鍵在于子節(jié)點的入棧順序，決定了子節(jié)點的出棧順序，
因為是前序遍歷 所以壓棧順序先讓右邊的入棧 依次往左 這樣左邊的節(jié)點會在棧頂 這樣下次優(yōu)先出棧的是左邊的元素 滿足前序遍歷

 for(int i = root.children.size()-1 ; i>=0 ;i--)stack.push(root.children.get(i));

class Solution {public List<Integer> preorder(Node root) {if(root==null) return new ArrayList<>();List<Integer> res = new ArrayList<>();Deque<Node> stack = new LinkedList<>();stack.push(root);while(!stack.isEmpty()){root  = stack.pop();res.add(root.val);//因為是前序遍歷  所以壓棧順序先讓右邊的入棧  依次往左  這樣左邊的節(jié)點會在棧頂 這樣下次優(yōu)先出棧的是左邊的元素 滿足前序遍歷for(int i = root.children.size()-1 ; i>=0 ;i--)stack.push(root.children.get(i));}return res;}
}

方法二：遞歸

原理和二叉樹的前序遍歷一樣 相當于把左右孩子 改成孩子集合了 孩子變多了而已，核心還是 根左右（先跟 再左孩子 在右孩子）

class Solution {List<Integer> res = new ArrayList<>();public List<Integer> preorder(Node root) {dfs(root);return res;}public void dfs(Node root){if(root == null) return;res.add(root.val);//前for(Node node : root.children)//中中中中中dfs(node);}
}