LeetCode 107. Binary Tree Level Order Traversal II

題目

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

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

翻譯

給一個二元樹，每一個階層從左到右裝成一個list，再從下到上放到一個大list裡面。

範例：
[3,9,20,null,null,15,7]

   3                          
  / \                         
 9   20                      
     / \                      
    15 17     

回傳

[
  [15,7],
  [9,20],
  [3]
]    

思路

1. 可以先去寫102. Binary Tree Level Order Traversal這題，兩題是一樣的，這題要再把102題最後的陣列反轉。這邊我們不用迴圈，改用遞迴來寫。
2. 先處理level 0 的root，將root做為第一個節點傳入遞迴function，當節點沒有left也沒有right的時候，停止遞迴。
3. 根據傳入的level，如果map裡面已經有該level的list，增加到裡面，如果沒有，map[level] = [node.val]。
4. 如果當前節點有子節點，先處理left，再處理right。
5. 不斷的重複3,4步驟值到沒有子節點。

   解題

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

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

    // 傳入root，level 0
    find(root,0);

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

    // 傳入node與level
    function find(node,level){
        if(node == null) return;
        // map[level]沒東西，map[level] = [node.val]
        if(!map[level]){
            map[level] = [node.val];
        } else {
            map[level].push(node.val);
        }

        // 先處理left，再處理right
        find(node.left,level+1);
        find(node.right,level+1);
    }


};