LeetCode 429. N-ary Tree Level Order Traversal

tags: leetcode Java Tree

Description

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

給定一個N叉樹，輸出這個數每個節點依照階層由左至右，由上至下

Example

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

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]]

Idea

• 運用BFS（廣度搜尋法）
• 使用Queue去由上至下遍歷放入每個節點，並在每層將節點poll^[1]出來

Code

/*
// 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<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> result = new LinkedList<>();
        if(root == null)
            return result;
        Queue<Node> queue = new LinkedList<Node>();
        queue.offer(root); 
        while(!queue.isEmpty()){ // queue如果空了代表每個節點都poll
        //一層迴圈代表處理一層level中的每個節點
            List<Integer> level_result = new LinkedList<>();
            int queue_size = queue.size(); //記錄這層的node個數
            for (int i = 0;i < queue_size;i++){
                Node n = queue.poll();
                level_result.add(n.val);//將節點的value加到此層的list上
                for (Node nn : n.children)//將目前此節點的children offer進去queue裏
                    queue.offer(nn);
            }
            result.add(level_result);
        }
        return result;
    }
}

---

1. poll是將queue裡第一個節點提取出來並在queue中刪除此節點。 ↩︎