题目

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

For example, given a 3-ary tree:

Return its preorder traversal as: [1,3,5,6,2,4].

Note:

Recursive solution is trivial, could you do it iteratively?

讲解

如果用递归来解题的话，还是非常简单的。如果要用迭代来解题，无非就是用栈来实现。要注意的一点是，需要一个额外的栈来把压栈的顺序倒一下序。

Java代码

递归代码：

/*// Definition for a Node.class Node {    public int val;    public List
    
      children;    public Node() {}    public Node(int _val,List
     
       _children) {        val = _val;        children = _children;    }};*/class Solution {    private List
      
        result = new ArrayList<>();    public List
       
         preorder(Node root) {        if(root==null){            return result;        }        result.add(root.val);        for(Node node:root.children){            preorder(node);        }        return result;    }}
       
      
     
    

迭代代码：

/*// Definition for a Node.class Node {    public int val;    public List
    
      children;    public Node() {}    public Node(int _val,List
     
       _children) {        val = _val;        children = _children;    }};*/class Solution {    private List
      
        result = new ArrayList<>();    private Stack
       
         stack = new Stack<>();    private Stack
        
          stack_temp = new Stack();    public List
         
           preorder(Node root) { if(root==null){ return result; } stack.push(root); while(!stack.empty()){ Node theNode = stack.pop(); result.add(theNode.val); for(Node node:theNode.children){ stack_temp.push(node); } while(!stack_temp.empty()){ stack.push(stack_temp.pop()); } } return result; }}