Finger Offer 32-ii. Print binary tree II from top to bottom

The title

The binary tree is printed from top to bottom layer, with nodes of the same layer printed from left to right, each layer printed to a row. For example, given a binary tree: [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7
Copy the code

Returns the result of its hierarchical traversal:

[[3], [9,20], [15,7]Copy the code

Their thinking

Depth-first traversal

The level variable was used to record the recursive level of the binary tree. Insert the enumerated binary tree node values into the specified level

code

var levelOrder = function (root) {
  const result = []
  helper(root, 0)
  return result
  function helper(node, level) {
    if (node === null) return
    if (result[level] === undefined) {
      result[level] = [node.val]
    } else [result[level].push(node.val)]

    helper(node.left, level + 1)
    helper(node.right, level + 1)}}Copy the code

Breadth-first traversal

Train of thought

Print all nodes of this layer to a line, and add all nodes of the next layer to the queue, and so on, can be divided into multi-line printing.

code

var levelOrder = function(root) {
    if(root === null) return []
    const result = [];
    let stack = [root];
    while(stack.length){
        const path = [];
        for(let i = stack.length-1 ; i >=0  ; i--){
            let temp = stack.shift();
            path.push(temp.val);
            temp.left && stack.push(temp.left)
            temp.right && stack.push(temp.right) 
        }
        result.push(path)
    }
    return result

};
Copy the code