589. N-ary Tree Preorder Traversal

Given an n-ary tree, return the preorder traversal of its nodes' values.

DFS:

class Solution {
    public List<Integer> preorder(Node root) {
        List<Integer> res = new ArrayList<>();
        if (root!=null) dfs(root,res);
        return res;
    }
    private void dfs(Node node, List<Integer> list){
        list.add(node.val);
        for(Node child : node.children){
            dfs(child, list);
        }
    }   
}

Iteration

class Solution {
    public List<Integer> preorder(Node root) {
        // use stack to mock dfs
        Stack<Node> stack = new Stack<>();
        List<Integer> res = new ArrayList<>();
        if (root == null) return res;
        stack.add(root);
        while (!stack.isEmpty()){
            Node node = stack.pop();
            res.add(node.val);
            // list support iterate from end to head
            for (int i=node.children.size()-1; i>=0; i--){
                stack.add(node.children.get(i));
            }
        }
        return res;
    }
}