LeetCode 102. Binary Tree Level Order Traversal

題目

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

For example: Given binary tree [3,9,20,null,null,15,7],

翻譯

給一個二元樹，每一個階層從左到右裝成一個列陣，再依序放到一個大的列陣裡面。

範例：  
[3,9,20,null,null,15,7]
   3                          
  / \                         
 9   20                      
     / \                      
    15 17     
回傳
[
  [3],
  [9,20],
  [15,7]
]    

思路

107. Binary Tree Level Order Traversal II 跟這題幾乎一樣，只是107要求的是下面階層的清單放在上面。這邊我們改用迴圈來解，步驟如下：

1. 用一個map來存放當前節點node的深度level與值val
2. 將node放到一個watinglist陣列裡面，一開始level為0
3. 取出watinglist內的node，如果map裡面已經有該level的陣列，增加到裡面，如果沒有，新增map[level]的新陣列
4. 如果node有子節點，level+1後放入watinglist裡面等處理
5. 處理watinglist下一個node值到沒有任何元素放在watinglist中

解題

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */


var levelOrder = function(root) {
    if(root === null || root.length === 0){
        return [];
    }

    // 使用map[level]的list儲存相同level節點的值
    var map = {};

    // 待處理節點的等待陣列，第一個要處理的當然就是root
    var waitlist = [ { level:0, node:root} ];

    // 處理到沒有待處理
    while(list.length > 0){

        // 取出waitlist最後一個node來處理
        var cur = waitlist.pop();
        var node = cur.node;

        // 如果當前node沒有其他同level的node，產生一個該level的list來裝
        if(!map[cur.level]){
            map[cur.level] = [node.val];
        } else {
            map[cur.level].push(node.val);
        }

        // 有子節點放入待處理清單，注意right要先放，因為上面是抓最後一個放入的節點處理，left後放才會被先處理
        if(node.right){
            waitlist.push({level:cur.level+1, node:node.right});
        }

        if(node.left){
            waitlist.push({level:cur.level+1, node:node.left});
        }

    }
    var result = [];

    for(var i in map){
        result.push(map[i]);
    }

    return result;
};

以上面的 [3,9,20,null,null,15,7]來看

1. 第一次執行時會將整個(node -> level:0，val:3)放入waitlist
2. 迴圈開始，抓出level:0，val:3的節點，發現map[0]沒有東西，因此map[0] = [3]
3. [3]的right[20]，level+1後放入waitlist，left[9]level+1後放入waitlist
4. 迴圈，取出最後放入的節點[9]，map[1] = [9]，[9]沒有子節點
5. 迴圈，取出剩下的[20]，map[1] = [9,20]，waitlist放入right[7], left[15]
6. 接下來迴圈繼續處理[15],[7]