#yyds幹貨盤點# leetcode算法題：N 叉樹的前序周遊

題目：

給定一個 n 叉樹的根節點  root ，傳回 其節點值的 前序周遊 。

n 叉樹 在輸入中按層序周遊進行序列化表示，每組子節點由空值 null 分隔（請參見示例）。

示例 1：

輸入：root = [1,null,3,2,4,null,5,6]

輸出：[1,3,5,6,2,4]

示例 2：

輸入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]

輸出：[1,2,3,6,7,11,14,4,8,12,5,9,13,10]

class Solution {
    public List<Integer> preorder(Node root) {
        List<Integer> res = new ArrayList<Integer>();
        if (root == null) {
            return res;
        }
        Map<Node, Integer> map = new HashMap<Node, Integer>();
        Deque<Node> stack = new ArrayDeque<Node>();
        Node node = root;
        while (!stack.isEmpty() || node != null) {
            while (node != null) {
                res.add(node.val);
                stack.push(node);
                List<Node> children = node.children;
                if (children != null && children.size() > 0) {
                    map.put(node, 0);
                    node = children.get(0);
                } else {
                    node = null;
                }
            }
            node = stack.peek();
            int index = map.getOrDefault(node, -1) + 1;
            List<Node> children = node.children;
            if (children != null && children.size() > index) {
                map.put(node, index);
                node = children.get(index);
            } else {
                stack.pop();
                map.remove(node);
                node = null;
            }
        }
        return res;
    }
}