589. N叉树的前序遍历

• 589. N叉树的前序遍历
• • 方法一：递归
  • 方法二：迭代

589. N叉树的前序遍历

方法一：递归

class Solution {
    public List<Integer> preorder(Node root) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        preorder(root, res);
        return res;
    }

    public void preorder(Node root, List<Integer> res) {
        if(root == null) {
            return;
        }
        res.add(root.val);
        if(root.children == null) {
            return;
        }
        for (Node child : root.children) {
            preorder(child, res);
        }
    }
}

方法二：迭代

class Solution {
    public List<Integer> preorder(Node root) {
        LinkedList<Node> stack = new LinkedList<>();
        LinkedList<Integer> output = new LinkedList<>();
        if (root == null) {
            return output;
        }
        stack.addLast(root); //push|add
        while (!stack.isEmpty()) {
            Node node = stack.pollLast(); //pop
            output.addLast(node.val);
            Collections.reverse(node.children);
            for (Node item : node.children) {
                stack.addLast(item);
            }
        }
        return output;
    }
}