25 二叉树的层级遍历（Binary Tree Level Order Traversal）

• • 1 题目
  • 2 解决方案
  • • 2.1 思路
    • 2.2 时间复杂度
    • 2.3 空间复杂度
  • 3 源码

题目：二叉树的层级遍历（Binary Tree Level Order Traversal）
描述：给出一棵二叉树，返回其节点值的层次遍历（逐层从左往右访问）

lintcode题号——69，难度——easy

样例1：

输入：tree = {1,2,3}
输出：[[1],[2,3]]
解释：
   1 
  /  
 2   3 
它将被序列化为{1,2,3}

样例2：

输入：tree = {1,#,2,3} 
输出：[[1],[2],[3]] 
解释：
1 
  
  2 
 / 
3 
它将被序列化为{1,#,2,3}

  使用宽度优先搜索进行层级遍历，由根节点引出第二层，再由第二层引出下一层，以此类推，标准的宽度优先搜索代码模版。

  二叉树宽度优先搜索，遍历所有的节点，算法的时间复杂度为O(n)。

  使用了queue队列数据结构保存节点，算法的空间复杂度为O(n)。

细节：

1. 使用queue队列数据结构，先进先出。
2. 如果不需要进行层级遍历，只需要按顺序遍历出所有节点，则去掉代码中的for循环即可。

C++版本：

vector> levelOrder(TreeNode *root) {
    // write your code here
    vector> results;
    if (root == nullptr)
    {
        return results;
    }

    queue nodeQueue;
    nodeQueue.push(root);
    while (!nodeQueue.empty())
    {
        vector level;
        int size = nodeQueue.size();
        for (int i = 0; i < size; i++)
        {
            TreeNode * cur = nodeQueue.front();
            nodeQueue.pop();
            level.push_back(cur->val);
            if (cur->left != nullptr)
            {
                nodeQueue.push(cur->left);
            }
            if (cur->right != nullptr)
            {
                nodeQueue.push(cur->right);
            }
        }
        results.push_back(level);
    }

    return results;
}