树的遍历

[lovelmh13]

树具有子结构，一旦涉及子问题，考虑使用「递归」完成。

中序遍历

�如果出现顺序的数组，要组成一个二叉搜索树，那么用中序遍历。因为 BST 的中序遍历是升序的。

层次遍历

关键使用「队列」，从左到右，从上到下的便利

const BFS = function(root) {
  if (!root) {
    return []
  }
  let queue = [root]
  const res = []
  while (queue.length > 0) {
      const node = queue.shift()
      res.push(node.val)
      
      if (node.left) {
        queue.push(node.left)
      }
      if (node.right) {
        queue.push(node.right)
      }
  }
  console.log(res)
  return res
}

步骤：

1. 创建一个队列。把 root 存进去
2. 循环队列，把 node 出队列。存入结果
3. 有左子树就把左子树压入队列
4. 有右子树就把右子树压入队列