# leetcode解題：(Easy) 589. N-ary Tree Preorder Traversal

題目：[https://leetcode.com/problems/n-ary-tree-preorder-traversal/](https://leetcode.com/problems/n-ary-tree-preorder-traversal/)

描述：用前序(Preorder)輸出N元樹(N-ary Tree)的數據

解題思路：遍歷樹的方法除了最簡單的遞迴法(recursive)外就是用迭代法(iterative)了，迴圈法通常都是用Stack實作

程式碼：

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
    public List<Integer> preorder(Node root) {
        List<Integer> result = new ArrayList<Integer>();
        if(root == null) return result;

        Stack<Node> stack = new Stack<Node>();
        stack.push(root);

        while(!stack.isEmpty()) {
            Node top = stack.pop();
            result.add(top.val);

            for(int i = top.children.size()-1; i >= 0; i--) {
                stack.push(top.children.get(i));
            }
        }

        return result;
    }
}

時間複雜度：O(n)
空間複雜度：O(n)

###### tags: `leetcode` `easy` `binary tree`