Brooke

一、題目

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

Nary-Tree input serialization is represented in their level order traversal. Each group of children is separated by the null value (See examples)

 

Example 1:

 

 

 

 

 

 

Input: root = [1,null,3,2,4,null,5,6] Output: [1,3,5,6,2,4]

Example 2:

 

 

 

 

 

 

 

Input: 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] Output: [1,2,3,6,7,11,14,4,8,12,5,9,13,10]

 

Constraints:

• The number of nodes in the tree is in the range [0, 104].
• 0 <= Node.val <= 104
• The height of the n-ary tree is less than or equal to 1000.

 

Follow up: Recursive solution is trivial, could you do it iteratively?

 

二、程式作法

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

    public Node() {}

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

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

/*use queue*/
public class Solution
{
    public IList<int> Preorder(Node root)
    {
        IList<int> res = new List<int>();
        Queue<Node> set = new Queue<Node>();
        if (root != null) set.Enqueue(root);

        while (set.Count > 0)
        {
            Node n = set.Dequeue();
            res.Add(n.val);
            int remain = set.Count;
            for (int i = 0; i < n.children.Count; i++)
                set.Enqueue(n.children[i]);
            for (int i = 0; i < remain; i++)
                set.Enqueue(set.Dequeue());
        }

        return res;
    }
}

/*use recursive*/
/*
public class Solution
{
    public IList<int> res = new List<int>();
    public IList<int> Preorder(Node root)
    {
        Helper(root);
        return res;
    }

    public void Helper(Node root)
    {
        if (root == null) return;
        else
        {
            res.Add(root.val);
            for (int i = 0; i < root.children.Count; i++)
                Helper(root.children[i]);
        }
    }
}
*/

 

三、思路筆記

這一題的input與其程式的Node結構我實在是兜不起來。

 

 

 

 

 

 

 

 

 

 

我想input只是用測試資料的表示法，但實際上還是要以程式上的Node結構去撰寫對應的程式。

 

有兩種作法一種是 recusive 另一種是 queue。