[algorithm][leetcode] 107. Binary Tree Level Order Traversal II

Runtime: 56 ms, faster than 82.45% of JavaScript online submissions for Binary Tree Level Order Traversal II.
Memory Usage: 34.7 MB, less than 100.00% of JavaScript online submissions for Binary Tree Level Order Traversal II.

/**
 * 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) {
// 1. brute force
//     root
//     root.left
//     root.right

//     root.left.left
//     root.left.right
//     root.right.left === null; done
//     root.right.right 

//     root.left.left.left === null; done
//     root.left.left.right === null; done
//     root.left.right.left === null; done
//     root.left.right.right === null; done
//     root.right.left x
//     root.right.left x
//     root.right.right.left
//     root.right.right.right === null; done

//     root.left.left.left x
//     root.left.left.left x
//     root.left.left.right x
//     root.left.left.right x
//     root.left.right.left x
//     root.left.right.left x
//     root.left.right.right x
//     root.left.right.right x
//     root.right.left x
//     root.right.left x
//     root.right.left x
//     root.right.left x
//     root.right.right.left.left === null; done
//     root.right.right.left.right === null; done
//     root.right.right.right x
//     root.right.right.right x
    
// 2. how to store them in an array?
//     [[root]]
//     [[root.left, root.right], [root]]
//     [[root.left.left, root.left.right, null, root.right.right], [root.left, root.right], [root]]
//     index == level

//  3. how to figure out which level is?
    // function has parameters, (Node, level) recursively searching        
    
    var res = [];
    pushValue(root, 0, res);
    return res.reverse();
};

function pushValue(node, level, res) {
    if (!node) return;
    
    // console.log(`>>> level:${level} =>`, res, 'root', node.val);
    res[level] = res[level] || [];
    res[level].push(node.val);
    
    level += 1;

    pushValue(node.left, level, res);
    pushValue(node.right, level, res);
}

실행순서

level:0 => [] root 3
level:1 => [ [ 3 ] ] root 9
level:1 => [ [ 3 ], [ 9 ] ] root 20
level:2 => [ [ 3 ], [ 9, 20 ] ] root 15
level:2 => [ [ 3 ], [ 9, 20 ], [ 15 ] ] root 7