当前位置：首页 > news >正文

【LeetCode】589.N叉树的前序遍历（递归+迭代，java实现，详细分析）

news 来源：原创 2024/5/2 7:04:26

题目

地址：

分析

方法一：递归

代码：

class Solution {
     List<Integer> list =new ArrayList<>();
    public List<Integer> preorder(Node root) {
     
        helper(root);
        return list;
    }
    private void helper(Node root){
        if(root == null) return;
        list.add(root.val);
        for(int i=0;i<root.children.size();i++)
            helper(root.children.get(i));
        return ;
    }
}

方法二：迭代

由于递归实现 N 叉树的前序遍历较为简单，因此我们只讲解如何使用迭代的方法得到 N 叉树的前序遍历。

我们使用一个栈来帮助我们得到前序遍历，需要保证栈顶的节点就是我们当前遍历到的节点。我们首先把根节点入栈，因为根节点是前序遍历中的第一个节点。随后每次我们从栈顶取出一个节点 u，它是我们当前遍历到的节点，并把 u 的所有子节点逆序推入栈中。例如 u 的子节点从左到右为 v1, v2, v3，那么推入栈的顺序应当为 v3, v2, v1，这样就保证了下一个遍历到的节点（即 u 的第一个子节点 v1）出现在栈顶的位置。

实现1：

class Solution {
    public List<Integer> preorder(Node root) {
        LinkedList<Node> stack = new LinkedList<>();
        LinkedList<Integer> output = new LinkedList<>();
        if (root == null) {
            return output;
        }

        stack.add(root);
        while (!stack.isEmpty()) {
            Node node = stack.pollLast();
            output.add(node.val);
            Collections.reverse(node.children);
            for (Node item : node.children) {
                stack.add(item);
            }
        }
        return output;
    }
}

实现2：

public List<Integer> preorder2(Node root) {
    List<Integer> res = new ArrayList<>();
    if (root == null) return res;
    Stack<Node> stack = new Stack<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        Node cur = stack.pop();
        //头结点加入结果集
        res.add(cur.val);
        //将该节点的子节点从右往左压入栈
        for (int i = cur.children.size() - 1; i >= 0; i--) {
            stack.push(cur.children.get(i));
        }
    }
    return res;
}