【LeetCode-简单题】589.N叉树的前序遍历

文章目录 题目方法一：单循环栈做法方法二：递归

题目

方法一：单循环栈做法

关键在于子节点的入栈顺序，决定了子节点的出栈顺序， 因为是前序遍历 所以压栈顺序先让右边的入栈 依次往左 这样左边的节点会在栈顶 这样下次优先出栈的是左边的元素 满足前序遍历

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); //因为是前序遍历 所以压栈顺序先让右边的入栈 依次往左 这样左边的节点会在栈顶 这样下次优先出栈的是左边的元素 满足前序遍历 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); } }