层序遍历（level order traversal）

在二叉树的 DFS 遍历中，我们以三种不同的顺序访问节点：前序、后序和中序。现在有另一种遍历方法，可以按层级顺序访问节点。这就是所谓的层序遍历或广度优先搜索遍历。简而言之，我们也叫它 BFS 遍历。

二叉树被组织成不同的层次，根节点位于最顶层（第 0 层）。所以层级遍历的想法是：我们从处理根节点开始，然后处理第一层、第二层的所有节点，以此类推。换句话说，我们先探索当前级别的所有节点，然后再进入下一级别的节点。

BFS 遍历的递归方法

这是一个蛮力的想法，我们使用一个循环从顶层移动到最底层，并使用递归处理每一层的节点。这个想法看起来很简单，但实施起来就有点麻烦了。讨论这种方法的目的是与解决问题有关的。在一些树形问题的递归解决中，有时我们会传递额外的参数或使用辅助函数来生成正确的输出。

递归 BFS 遍历的实现：

• 层次的数量等于树的高度。所以我们首先用函数 height (root) 计算树的高度 h。
• 我们运行一个从 l=0 到 h-1 的循环，并访问树中的每一层。在这个循环中，我们使用函数 processCurrentLevel (root, l) 来访问和处理当前级别 l 的节点。

我们如何实现函数 processCurrentLevel (root, l)？让我们思考一下！我们可以把这个问题分成两部分:

• 我们处理左侧子树中 l 级的所有节点。为此，我们用 root->left 和 l - 1 作为函数参数调用同一个函数。为什么？因为，如果当前级别与根的距离是 l，那么它与根 -> 左的距离将是 l - 1。
• 我们处理右边子树中 l 级的所有节点。为此，我们用 root->right 和 l - 1 作为函数参数调用同一个函数。为什么？因为，如果当前级别与根的距离是 l，那么它与根 -> 右的距离将是 l - 1。
• 在递归调用过程中，当 l == 0 时，我们到达一个节点，该节点与根的距离为 l。所以我们处理这个节点。通过这种方式，我们可以递归地访问 l 层的所有节点。

伪代码：

class TreeNode
{
    int data
    TreeNode left 
    TreeNode right
}
 
void recursiveLevelOrder(TreeNode root)
{
    int h = height(root)
    for (int l = 0; l < h; l = l + 1)
        processCurrentLevel(root, l)
}

void processCurrentLevel(TreeNode root, int l)
{
    if (root == NULL)
        return
    if (l == 0)
        process(root->data)
    else if (l > 0)
    {
        processCurrentLevel(root->left, l - 1)
        processCurrentLevel(root->right, l - 1)
    }
}

int height(TreeNode root)
{
    if (root == NULL)
        return 0
    else
    {
        int leftHeight = height(root->left)
        int rightHeight = height(root->right)
        
        if (leftHeight > rightHeight)
            return (rightHeight + 1)
        else 
            return(rightHeight + 1)
    }
}

时间和空间复杂性分析：

对于每一次递归调用 processCurrentLevel ()，我们都要在左右子树中向下移动 l-1 级。换句话说，我们正在访问从 0 级到 l 级的每个节点，并检查 l==0 与否。所以有一个想法很清楚：操作的总数取决于树的高度。

最坏的情况是倾斜的树，每层都有一个节点。在这种情况下，processCurrentLevel () 对最后一层需要 O (n) 时间，对倒数第二层需要 O (n-1) 时间，以此类推。这里 n 是树中的节点数。时间复杂性 = O(n) + O(n-1) + ... + O(1) = O(n + (n-1) + ...+ 1) = O(n^2) 。

在最坏的情况下，空间复杂度 = O (n)。对于一棵倾斜的树，processCurrentLevel () 将使用 O (n) 空间作为调用栈。对于一个平衡树，调用栈使用 O (log n) 空间（这等于平衡树的高度）。

使用队列的 BFS 遍历

现在的关键问题是，我们能优化 BFS 遍历的时间复杂性吗？我们能以 O (n) 的时间复杂度逐级遍历树吗？让我们观察一下层级遍历中的节点顺序。

• 我们首先处理第 0 层的根节点，然后处理第 1 层的左、右子节点（假设从左到右的顺序）。
• 同样地，在第二层，我们首先处理根节点的左子节点的子节点，然后处理右子节点的子节点。这个过程对树中的所有级别都是如此。

因此，有一个想法是明确的：在任何给定的级别，节点将被首先处理，该节点的子女将在下一级被首先处理。这是处理节点的先入先出顺序（FIFO 顺序）。所以我们可以使用队列数据结构来模拟 BFS 遍历。

使用队列进行 BFS 遍历的实施步骤：

• 我们取一个空的队列 treeQueue，并用根节点初始化它。
• 现在我们运行一个循环，直到 treeQueue 不为空。
• 在这个循环中，我们声明一个 currNode，以便在遍历过程中跟踪当前节点。
• 我们开始循环，从 treeQueue 中移除前端节点，并将其分配给 currNode。我们处理 currNode，并将左右两个子节点插入到 treeQueue 中。

TreeNode currNode = treeQueue.dequeue()
process (currNode->data)

• 如果 currNode 的左侧子节点不是 NULL，我们将左侧子节点插入到 treeQueue 中。

if (currNode->left != NULL)
  treeQueue.enqueue(currNode->left)

• 如果 currNode 的右边的孩子不是 NULL，我们就把右边的孩子插入到 treeQueue 中。

if (currNode->right != NULL)
  treeQueue.enqueue(currNode->right)

在处理完最后一级的最右边的节点后，队列里面就没有节点可以继续处理了。所以我们从循环中出来，我们的层序遍历在这时完成。

伪代码：

void iterativeLevelOrder(Treenode root)
{
    if (root == NULL)  
        return
    Queue<TreeNode> treeQueue
    treeQueue.enqueue(root)
    while (treeQueue.empty() == false)
    {
        TreeNode currNode = treeQueue.dequeue()
        process(currNode->data) 
        
        if (currNode->left != NULL)
            treeQueue.enqueue(currNode->left)
 
        if (currNode->right != NULL)
            treeQueue.enqueue(currNode->right)
    }
}

BFS 遍历的时间复杂性分析：

• 假设输入中有 n 个节点。
• enqueue 和 dequeue 操作的时间复杂度 = O (1)
• 我们在循环内为每个节点做两次队列操作。向队列中插入一次，从队列中删除一次。所以总的队列操作 = 2n。
• 总体时间复杂度 = 总队列操作 * 每个队列操作的时间复杂度 = 2n * O (1) = O (n)

BFS 遍历的空间复杂度分析：

空间复杂度等于队列大小。我们逐级处理节点，所以最大队列大小取决于具有最大节点数或二叉树最大宽度的层级。如果二叉树的最大宽度是 w，那么空间复杂度 = O（w）。这个想法很简单：w 取决于给定二叉树的结构。

最坏的情况：当树是平衡的，最后一层将有最大的宽度或最大的节点数，这将是 2^h（其中 h 是树的高度）。对于平衡树，h=logn，所需的队列大小 = O (2^h) = O (2 ^ (log n)) = O (n)。空间复杂度 = O (n)

最好的情况：当树是倾斜的，在这种情况下，每一层最多只有一个节点，因此在任何一点，队列中最多只有一个节点。因此需要的队列大小 = O (1)。空间复杂度 = O (1)。

二叉树的 BFS 遍历 vs DFS 遍历

• 这两种遍历方法都需要 O (n) 时间，因为它们对每个节点都正好访问一次。
• 深度优先遍历从根部开始，尽可能地深入，然后从那里回溯。换句话说，它从树的底部访问节点。但在广度优先搜索中，我们逐级探索节点，即按照它们与根节点的距离排序。因此，如果我们的问题是要搜索离根更近的东西，我们会选择 BFS。而如果我们需要在树的深度或靠近叶子的节点中搜索一些东西，我们会选择 DFS。
• 在 BFS 遍历中，我们使用队列数据结构来存储不同层次的节点。但是在 DFS 遍历中，我们使用堆栈（如果是递归，系统使用调用堆栈）来存储一个节点的所有祖先。
• BFS 和 DFS 所占用的内存都取决于树的结构。BFS 遍历所需的额外空间是 O (w)，但 DFS 遍历所需的额外空间是 O (h)。这里 w = 二叉树的最大宽度，h = 二叉树的最大高度。在最坏的情况下，两者都需要 O (n) 的额外空间，但最坏的情况发生在不同类型的树。例如，当树比较平衡时，BFS 遍历需要的空间可能会更多，而当树不太平衡时，DFS 遍历的额外空间可能会更多。
• 有时，当解决问题时不需要节点顺序，我们可以同时使用 BFS 和 DFS 遍历。但在某些情况下，这种事情是不可能的。我们需要确定遍历的使用情况，以便有效地解决问题。

实现

JavaScript

/*
  Breadth First Tree Traversal or level order traversal implementation in javascript
  Author: @GerardUbuntu
*/

class Node {
  constructor (data) {
    this.data = data
    this.left = null
    this.right = null
  }
}

class BinaryTree {
  constructor () {
    this.root = null
    this.traversal = []
  }

  breadthFirst () {
    const h = this.getHeight(this.root)
    for (let i = 0; i !== h; i++) {
      this.traverseLevel(this.root, i)
    }
    return this.traversal
  }

  // Computing the height of the tree
  getHeight (node) {
    if (node === null) {
      return 0
    }
    const lheight = this.getHeight(node.left)
    const rheight = this.getHeight(node.right)
    return lheight > rheight ? lheight + 1 : rheight + 1
  }

  traverseLevel (node, levelRemaining) {
    if (node === null) {
      return
    }
    if (levelRemaining === 0) {
      this.traversal.push(node.data)
    } else {
      this.traverseLevel(node.left, levelRemaining - 1)
      this.traverseLevel(node.right, levelRemaining - 1)
    }
  }
}

参考

• Level Order Traversal (BFS Traversal) of a Binary Tree (opens new window)
• BreadthFirstSearch [广度优先搜索 / BFS] | Fancy DSA