28 - 二叉树层次遍历1

题目

给定一个二叉树，返回其按层次遍历的节点值。 （即逐层地，从左到右访问所有节点）。

例如: 给定二叉树: [3,9,20,null,null,15,7],

​ 3 / 9 20 ​ / 15 7

返回其层次遍历结果：

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

解答

迭代

思路就是一层层处理。每一层都记录一下val和下一层需要判断的节点。

var levelOrder = function (root) {
  if (!root) {
    return []
  }
  let stack = [root]
  let result = []
  let level = []
  let stack_tmp = []
  while (stack.length > 0) {
    for (let i = 0; i < stack.length; i++) {
      const cur = stack[i]
      level.push(cur.val)
      if (cur.left) {
        stack_tmp.push(cur.left)
      }
      if (cur.right) {
        stack_tmp.push(cur.right)
      }
    }
    result.push(level)
    stack = stack_tmp
    level = []
    stack_tmp = []
  }
  return result 
};

Runtime: 56 ms, faster than 79.77% of JavaScript online submissions for Binary Tree Level Order Traversal.

Memory Usage: 34.8 MB, less than 90.67% of JavaScript online submissions for Binary Tree Level Order Traversal.

level和stack_tmp是用来过渡的。level存本层的val，最后推进result，作为最终的结果返回；stack_tmp用来存放下一个层需要记录的节点val。

因为这个堆栈是后入先出，如果直接把.left或.right推进stack，那么就会直接把下一层节点val都记录了。

推入stack_tmp的顺序，也得因此是先左后右，因为每一层要从左至右地记录val。

递归

作者：yagamilight126

链接：https://leetcode-cn.com/problems/two-sum/solution/jsde-dfsjie-fa-by-yagamilight126/

var levelOrder = function (root) {
  if (!root) {
    return []
  }
  let result = []
  const traverse = (node, level) => {
    if (node !== null) {
      result[level] ? result[level].push(node.val) : result[level] = [node.val];
      traverse(node.left, level + 1);
      traverse(node.right, level + 1);
    }
  }
  traverse(root, 0);
  return result;
};

Runtime: 60 ms, faster than 62.05% of JavaScript online submissions for Binary Tree Level Order Traversal.

Memory Usage: 35 MB, less than 22.44% of JavaScript online submissions for Binary Tree Level Order Traversal.

多定义一个traverse函数，传入一个level，记录所在层数。感觉很厉害。

如果result中该层里面没有预先定义的数组，就加上，不然就往里面push新的值

测试代码

很想吐槽一下，这是个鬼的二叉树

image-20190723223239014

9明明比3大，为什么在3的左边？我一开始生成BST的代码，结果怎么都对不上。。

按照力扣给的数组[3, 9, 20, null, null, 15, 7]，大意是直接根据数组的左右插入即可。也是一个广度优先的遍历二叉树。

【测试代码有点难写。。最终是在官网在线测的。。】