[LeetCode刷題筆記] 429 - N-ary Tree Level Order Traversal

題目描述：

Given an n-ary tree, return the level order 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,2,4],[5,6]]

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,4,5],[6,7,8,9,10],[11,12,13],[14]]

Constraints:

• The height of the n-ary tree is less than or equal to 1000
• The total number of nodes is between [0, 104]

一刷題解（Iteration）：

這題雖然也是N叉樹的遍歷，但是做起來與前後序遍歷不一樣。對於N叉樹的前後序遍歷而言，直接通過遍歷每個子樹進行Recursion來完成來要容易的多。就像下面這樣：

前序遍歷

public class Solution {
    public IList<int> Preorder(Node root) {
        List<int> res = new List<int>();
        PreorderHelper(res, root);
        return res;
    }
    
    void PreorderHelper(List<int> res, Node root)
    {
        if(root == null) { return; }
        //當前節點
        res.Add(root.val);
        //從左往右
        for (int i = 0; i < root.children.Count; i++)
        {
            PreorderHelper(res, root.children[i]);
        }            
    }    
}

後序遍歷

public class Solution {
    public IList<int> Postorder(Node root) {
        List<int> res = new List<int>();
        PostorderHelper(res, root);
        return res;        
    }
    void PostorderHelper(List<int> res, Node root)
    {
        if (root == null) { return; }
        //從左往右
foreach (var node in root.children)
        {
            PostorderHelper(res, node);
        }
        //當前節點
        res.Add(root.val);
    }    
}

但是要做層序遍歷的話，使用Iteration的邏輯會更容易理順。通過持續把每層節點加到一個隊列中，然後再遍歷當層子節點數量的次數，把當層子節點出列，將這些子節點的下一層節點入列，直到再沒有節點加到隊列中為止，這個N叉樹也就遍歷完結。

public class Solution {
    public IList<IList<int>> LevelOrder(Node root) {
        
        List<IList<int>> res = new List<IList<int>>();

        if(root == null) { return res; }
        
        //只有這個隊列還有元素，代表還有一層
        Queue<Node> nodeQ = new Queue<Node>();
        nodeQ.Enqueue(root);

        //當層節點列表和數量
        List<int> currStair;
        int stairNodeCnt = 0;

        while(nodeQ.Count > 0)
        {            
            currStair = new List<int>();
            //每一層的節點數量 = 每一次開始遍歷隊列時的隊列元素數量
            stairNodeCnt = nodeQ.Count;

            //遍歷{當層節點數量}次
            while(stairNodeCnt > 0)
            {
                Node curr = nodeQ.Dequeue();
                //把節點放到當層的結果列表
                currStair.Add(curr.val);
                //把子節點入隊
                foreach (Node child in curr.children)
                {
                    if(child != null)
                    {
                        nodeQ.Enqueue(child);
                    }
                }
                stairNodeCnt--;
            }
            //完成一層的遍歷
            res.Add(currStair);
        }

        return res;        
    }
}