2024.2.18力扣每日一题——N叉树的前序遍历

题目来源

力扣每日一题；题序：589

我的题解

方法一 深度优先遍历（递归方式）

与二叉树的前序遍历相似，只是遍历子节点的细节不同

时间复杂度：O(n)
空间复杂度：O(n)

public List<Integer> preorder(Node root) {List<Integer> res=new ArrayList<>();pre(root,res);return res;
}
public void pre(Node root,List<Integer> res){if(root==null)return;res.add(root.val);//与二叉树前序遍历不同的细节之处for(Node node:root.children){pre(node,res);}
}

方法二 迭代方式（栈实现）

与二叉树的迭代方式相同，细节有所不同

时间复杂度：O(n)
空间复杂度：On()

public List<Integer> preorder(Node root) {List<Integer> res=new ArrayList<>();if(root==null)return res;LinkedList<Node> stack=new LinkedList<>();stack.push(root);while(!stack.isEmpty()){Node t=stack.pop();res.add(t.val);//细节的不同，需要将同一个父节点的所有子节点按照从右到左的顺序入栈for(int i=t.children.size()-1;i>=0;i--){Node node=t.children.get(i);stack.push(node);}}return res;
}

有任何问题，欢迎评论区交流，欢迎评论区提供其它解题思路（代码），也可以点个赞支持一下作者哈😄~