[leetCode]589. N叉树的前序遍历

题目

https://leetcode-cn.com/problems/n-ary-tree-preorder-traversal/

给定一个 N 叉树，返回其节点值的前序遍历。

例如，给定一个 3叉树 :

返回其前序遍历: [1,3,5,6,2,4]。

递归

class Solution {
    List<Integer> ans = new ArrayList<>();

    public List<Integer> preorder(Node root) {
        traversal(root);
        return ans;
    }

    private void traversal(Node node) {
        if (node == null) 
            return;
        ans.add(node.val);
        for (Node c : node.children) {
            traversal(c);
        }
    }
}

迭代

class Solution {
    List<Integer> ans = new ArrayList<>();

    public List<Integer> preorder(Node root) {
        if (root == null) return ans;
        LinkedList<Node> stack = new LinkedList<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            Node node = stack.pop();
            if (node != null) {
                for (int i = node.children.size() -1; i >= 0; i--) {
                    if (node.children.get(i) != null)
                        stack.push(node.children.get(i));
                }
                stack.push(node);
                stack.push(null);
            } else {
                Node cur = stack.pop();
                ans.add(cur.val);
            }
        }
        return ans;
    }
}