二叉树的层次遍历

在计算机科学中，二叉树是一种常见的数据结构。二叉树由节点组成，每个节点最多有两个子节点，分别称为左子节点和右子节点。树的层次遍历是一种广度优先的遍历方式，从根节点开始，按层次依次访问树的节点。

算法思路

我们可以使用队列来实现二叉树的层次遍历。首先将根节点加入队列，然后循环以下步骤直到队列为空：

1. 从队列中取出一个节点。
2. 访问该节点。
3. 将该节点的子节点（如果有）加入队列。

这样，我们就可以按层次遍历二叉树了。

算法实现

下面是二叉树层次遍历的实现代码：

class TreeNode {
  int val;
  TreeNode left;
  TreeNode right;

  TreeNode(int val) {
    this.val = val;
  }
}

List> levelOrder(TreeNode root) {
  List> resultList = new ArrayList<>();
  
  if (root == null) {
    return resultList;
  }
  
  Queue queue = new LinkedList<>();
  queue.offer(root);

  while (!queue.isEmpty()) {
    int levelSize = queue.size();
    List levelList = new ArrayList<>();

    for (int i = 0; i < levelSize; i++) {
      TreeNode node = queue.poll();
      levelList.add(node.val);

      if (node.left != null) {
        queue.offer(node.left);
      }

      if (node.right != null) {
        queue.offer(node.right);
      }
    }

    resultList.add(levelList);
  }

  return resultList;
}

上述代码中，我们首先判断根节点是否为空，如果为空则直接返回空列表。接下来，我们创建一个队列，并将根节点加入队列。然后，我们开始循环，直到队列为空。在每一次循环中，我们通过队列弹出一个节点，并将其值加入当前层的列表。然后，我们将该节点的子节点加入队列。最后，我们将当前层的列表加入结果列表。循环结束后，我们就可以得到二叉树的层次遍历结果。

总结

二叉树的层次遍历是一种基于广度优先的遍历方式，可以按层次访问二叉树的节点。通过使用队列，我们可以方便地实现二叉树的层次遍历算法。这种算法的时间复杂度为O(n)，其中n为二叉树的节点个数。

通过以上的算法实现，我们可以轻松地解决二叉树的层次遍历问题。这种遍历方式可以帮助我们更好地理解二叉树的结构，并能在一定程度上简化相关问题的处理。

如果你对二叉树的层次遍历算法还有其他疑问或者想要分享更多相关内容，请在下方留言，让我们一起探讨。