二叉树怎样层序遍历、求最大深度？

简答

二叉树的每个节点最多有左右两个子节点。遍历方式分两大类：深度优先是一条路走到底再回头，前序、中序、后序都属于这一类；广度优先是一层一层往下走，也叫层序遍历。

层序遍历靠队列，队列是先进先出的。先把根节点放进去，然后循环：记下当前队列里有几个节点，这些就是同一层的；依次取出它们，记录值，再把它们的左右子节点放到队尾。这一轮处理完，队列里剩下的正好是下一层。所以输出可以按层分组。

最大深度是从根到最远叶子节点经过的节点数。递归写法最短：空节点深度是 0，否则就是左右子树深度的较大值加 1。也可以直接做层序遍历，数一共有几层。

要注意，用数组的 shift() 当队列出队，每次都要把后面的元素往前挪，大数据量时会变慢。节点很多时可以用一个下标记录队头位置，代替 shift()。

代码实现

const tree = {
  value: 1,
  left: { value: 2, left: { value: 4 }, right: { value: 5 } },
  right: { value: 3, right: { value: 6 } },
};

function levelOrder(root) {
  if (!root) return [];
  const result = [];
  const queue = [root];
  let head = 0;
  while (head < queue.length) {
    const size = queue.length - head;
    const level = [];
    for (let i = 0; i < size; i++) {
      const node = queue[head++];
      level.push(node.value);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    result.push(level);
  }
  return result;
}

function maxDepth(node) {
  if (!node) return 0;
  return Math.max(maxDepth(node.left), maxDepth(node.right)) + 1;
}

console.log(JSON.stringify(levelOrder(tree))); // [[1],[2,3],[4,5,6]]
console.log(maxDepth(tree)); // 3
console.log(maxDepth(null)); // 0

为什么要在每一轮开始时先算出 size？因为循环里会往队列追加下一层的节点，队列长度一直在变。提前记下这一层有几个，才知道取到哪里为止是同一层，结果才能按层分组。

这里没有用 shift()，而是用 head 记录队头的位置，出队就是 head++。数组前面已经处理过的元素不删，每次出队都是 O(1)，整体遍历是 O(n)。

maxDepth 的递归怎么理解？节点 2 的左右子节点 4、5 深度都是 1，所以节点 2 深度是 2；节点 3 只有右子节点 6，深度也是 2；根节点取较大的 2 再加 1，就是 3。

前端哪里用得到

DOM 树、组件树、菜单和组织架构树都是树。按层展开、找离某个节点最近的匹配项，用广度优先；渲染嵌套菜单、序列化整棵树，常用深度优先。显式栈写法的深度优先见《怎样用显式栈实现树的前序遍历？》，把扁平列表转成树见《怎样在 O(n) 时间内把扁平列表转成树，再把树转回列表？》。

常见追问

中序遍历有什么特别的用途？

二叉搜索树的左子树都比根小、右子树都比根大，中序遍历的顺序是左、根、右，正好得到从小到大的有序序列。所以判断一棵树是不是二叉搜索树，可以看中序遍历结果是不是递增的。

怎样翻转二叉树？

对每个节点交换它的左右子节点，再递归处理左右子树。递归、层序遍历都可以，每个节点处理一次，O(n)。