LC429-N 叉樹的層序周遊

​​429. N 叉樹的層序周遊​​

LC102-二叉樹的層序周遊 難度中等126

給定一個 N 叉樹，傳回其節點值的層序周遊。（即從左到右，逐層周遊）。

樹的序列化輸入是用層序周遊，每組子節點都由 null 值分隔（參見示例）。

示例 1：

輸入：root = [1,null,3,2,4,null,5,6]
輸出：[[1],[3,2,4],[5,6]]      

​​官方詳細圖解​​

基本算法。

利用隊列實作廣度優先搜尋

• 樹上使用基于隊列的周遊算法，看看它的作用。這是你應該記住的一個基本算法。
• 我們要構造一個​

  ​sub-lists​

  ​​ 清單，其中每個​

  ​sub-list​

  ​ 是樹中一行的值。行應該按從上到下的順序排列。
• 由根節點開始周遊樹,然後向下搜尋接近根節點的節點, 這就是廣度優先搜尋
• 使用隊列來進行廣度優先搜尋,隊列具有先進先出的特性
• 在這裡使用棧是錯誤的選擇，棧應用于深度優先搜尋。

List<Integer> values = new ArrayList<>();
Queue<Node> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
    Node nextNode = queue.remove();
    values.add(nextNode.val);
    for (Node child : nextNode.children) {
        queue.add(child);
    }
}      

算法:

需要儲存每一層的清單,并且在根節點為空時正常工作

在構造下一層的清單時,我們需要建立新的子清單，然後将該層的所有節點的值插入到清單中。

​

​while​

​​ 循環體開始時記錄隊列的目前大小 ​

​size​

​​。 然後用另外一個循環來處理​

​size​

​​ 數量的節點。這樣可以保證 ​

​while​

​ 循環在每一次疊代處理一層。

public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            List<Integer> level = new ArrayList<>();
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                Node node = queue.poll();
                level.add(node.val);
                for (Node item : node.children) {
                        queue.add(item);
                }
            }
            result.add(level);
        }
        return result;
    }      

複雜度分析

• 時間複雜度：O(n)。n指的是節點的數量。
• 空間複雜度：O(n)

方法二：簡化的廣度優先搜尋\

看官方題解

​​官方詳細圖解​​

方法三：遞歸深度優先搜尋

class Solution {

    private List<List<Integer>> result = new ArrayList<>();

    public List<List<Integer>> levelOrder(Node root) {
        if (root != null) traverseNode(root, 0);
        return result;
    }

    private void traverseNode(Node node, int level) {
        if (result.size() <= level) {
            result.add(new ArrayList<>());
        }
        result.get(level).add(node.val);
        for (Node child : node.children) {
            traverseNode(child, level + 1);
        }
    }
}