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);
    }


};

results matching ""

    No results matching ""