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);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

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

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

时间复杂度：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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

有任何问题，欢迎评论区交流，欢迎评论区提供其它解题思路（代码），也可以点个赞支持一下作者哈 本文内容由网友自发贡献，转载请注明出处：https://www.wpsshop.cn/w/从前慢现在也慢/article/detail/352266