leetcode-二叉树-层序遍历

一、模板

1. 递归

/**
 * 递归-通用层序遍历模板
 */

/** 
 * 层序遍历1 一个一个处理
 */

var problem = (root) => {
  // 0. prepare
  let res = []
  if (root === null) return res
  const queue = [[root, 0]]
  while (queue.length) { // 1. terminator 终止条件
    // 2. process logic in current shift node 处理当前出队元素的逻辑 
    const [cur, depth] = queue.shift()
    if (!res[depth]) res[depth] = []
    else res[depth].push(cur.val)

    // 3. push
    if (node.left) queue.push(node.left)

    // 4. push
    if (node.right) queue.push(node.right)

    // 5. reverse the current status if needed
  }
  return res
}

/** 
 * 层序遍历2 一层一层处理
 */

var problem = (root) => {
  // 0. prepare
  let res = []
  if (root === null) return res
  const queue = [[root, 0]]
  while (queue.length) { // 1. terminator 终止条件
    let len = queue.length
    for (let i = 0; i < len; i++) {
      // 2. process logic in current shift node 处理当前出队元素的逻辑 
      const [cur, depth] = queue.shift()
      if (!res[depth]) res[depth] = []
      else res[depth].push(cur.val)

      // 3. push
      if (node.left) queue.push(node.left)

      // 4. push
      if (node.right) queue.push(node.right)
    }

    // 5. reverse the current status if needed
  }
  return res
}

二、题目

102. 二叉树的层序遍历

/**
 * bfs1
 */

var levelOrder = function (root) {
  const ret = []
  if(!root) return ret

  const q = [[root,0]]
  while(q.length){
    const [cur,depth] = q.shift()
    
    if(!ret[depth])  ret[depth] = [cur.val]
    else  ret[depth].push(cur.val)

    if(cur.left)  q.push([cur.left,depth+1])
    if(cur.right)  q.push([cur.right,depth+1])
  }
  
  return ret
};

/**
 * bfs2 
 */

var levelOrder = function (root) {
  const ret = []
  if (!root) return ret

  const q = [root]
  while (q.length) {
    let len = q.length
    ret.push([])
    for (let i = 0; i < len; i++) {
      const cur = q.shift()
      ret[ret.length-1].push(cur.val)
      if (cur.left) q.push(cur.left)
      if (cur.right) q.push(cur.right)
    }
  }

  return ret
};

/**
 * dfs
 */

var levelOrder = function (root) {
  const ret = []
  if (!root) return ret
  dfs(root,0)
  return ret

  function dfs(root,depth){
    if(root === null) return

    if(ret[depth])
      ret[depth].push(root.val)
    else
      ret[depth] = [root.val]
    dfs(root.left,depth+1)
    dfs(root.right,depth+1)
  }
};

429. N 叉树的层序遍历

/**
 * bfs
 */

var levelOrder = function (root) {
  const ret = []
  if (!root) return ret

  const queue = [[root, 0]]
  while (queue.length) {
    const [cur, depth] = queue.shift()
    if (!ret[depth]) ret[depth] = [cur.val]
    else ret[depth].push(cur.val)

    for (let i = 0; i < cur.children.length; i++)
      queue.push([cur.children[i], depth + 1])
  }

  return ret
};

/**
 * bfs
 */

var levelOrder = function (root) {
  const ret = []
  if (!root) return ret

  const queue = [root]
  while (queue.length) {
    let len = queue.length
    ret.push([])
    for(let i = 0;i<len;i++){
      const cur = queue.shift()
      ret[ret.length-1].push(cur.val)

      for(let i = 0;i<cur.children.length;i++)
        queue.push(cur.children[i])
    }
  }

  return ret
};