【102. 二叉树的层序遍历 中等】

题目：

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]

示例 2：
输入：root = [1]
输出：[[1]]

示例 3：
输入：root = []
输出：[]

提示：

• 树中节点数目在范围 [0, 2000] 内
• -1000 <= Node.val <= 1000

思路：

层序遍历一个二叉树。就是从左到右一层一层的去遍历二叉树。这种遍历的方式和之前讲过的都不太一样。

需要借用一个辅助数据结构即队列来实现，队列先进先出，符合一层一层遍历的逻辑，而用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。

而这种层序遍历方式就是图论中的广度优先遍历，只不过我们应用在二叉树上。

使用队列实现二叉树广度优先遍历，动画如下：

代码：

1. 方法1：借助队列queue实现迭代遍历

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*>  que1;
        if(root != NULL) que1.push(root);
        vector<vector<int>> result;

        while(!que1.empty()){
            int size = que1.size();
            vector<int> vec;
            // 这里一定要使用固定大小size，不要使用que.size()，因为que.size是不断变化的
            while(size--){	//	一个循环对应一层深度
                TreeNode* node = que1.front();
                que1.pop();
                vec.push_back(node->val);    //  将该层的节点存入该层vector中
                if(node->left) que1.push(node->left);   //  将该层节点的左子节点存入queue中，下次循环取出存入vector
                if(node->right) que1.push(node->right); //  将该层节点的右子节点存入queue中，下次循环取出存入vector
            }
            result.push_back(vec);  //将该层vector存储到result中
        }
        return result;
    }
};

2. 方法2：递归遍历。递归算法的三要素参考【递归法：144.二叉树的前序遍历 145.二叉树的后序遍历 94.二叉树的中序遍历 简单】

class Solution {
public:
    void order(TreeNode* cur, vector<vector<int>>& result, int depth){
        if(cur == NULL) return;
        //  确保在向 result 添加节点之前，每个深度都有一个对应的向量来存储该层级的节点值，从而避免越界访问和未定义行为。
        if(result.size() == depth) result.push_back(vector<int> ());
        result[depth].push_back(cur->val);
        order(cur->left, result, depth + 1);
        order(cur->right, result, depth + 1);
    }
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> result;
        int depth = 0;
        order(root, result, depth);
        return result;
    }
};

总结：

这份代码也可以作为二叉树层序遍历的模板。

参考：

代码随想录