102.二叉树的层序遍历.md

/**

 * Definition for a binary tree node.
 * struct TreeNode {
 * int val;
 * TreeNode *left;
 * TreeNode *right;
 * TreeNode() : val(0), left(nullptr), right(nullptr) {}
 * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
   */

二叉树 迭代 广度优先搜索 BFS 层序遍历 队列

思路：经典-二叉树层序遍历-迭代(BFS)解法。此题是广度优先搜索，即一层搜完了再进入下一层，这点上很容易理解。

注：此题为“二叉树-广度优先搜索”的模板，需要理解并记住用“队列”完成该“层序遍历”的方式。
注：画图理解队列的运作很重要，P154。

注：两层循环while()-for()。“每一层while()代表一个阶段”，每一阶段都将二叉树的这一层的“本阶段成果vec”“用result”记录下来。
即result.push_back(vec)。for()遍历“当前阶段的队列que”，遍历过程中将“本阶段队列que”中的“节点node们”依次剔除，
并依次存入“本阶段成果vec”中，然后再将“下一阶段的节点node们”“先左后右”地加入队列que，再等下一个阶段的while()循环使用。

注：vec<vec> result(int)用来记录总结果，其由“每一阶段的结果vec(int)组成”。que(node*)用来记录“每一阶段的node们”，
是动态变化的，如果“上阶段的node们被剔除，下阶段的node们就会进来”，在for()内完成。“que和vec存在先后关系”，
在当前阶段遍历node们时，总是先que推出node，然后vec去记录该node，然后que去记录该node的下一阶段node，这其实就是for()内逻辑。

还有一点注意，就是que此时去记录“当前node的下一阶段node们”时，一般“当前阶段的node们还没完全推出”，就会存在que内
“既有当前阶段又有下一阶段的node”，但这不影响，因为下一阶段的node们进来后，是排在que后面的，无所谓。
其实这也是for()在遍历过程中正常会出现的情况，一旦一个完整for()遍历完，即经过一个完整while()，上述情况就不存在了，
que内此时必然全装的是“干净的下一阶段的node们”了。

1：第一个node，即root*，是在while()外推入队列que的，这也体现了上述que的“领先”思想。
2：vec的初始化位置，是在while()内for()外，因为vec是记录每个完整for的阶段性成果的，即每个阶段的node们。
3：由于que在每次for()内动态变化，所以要在for外用“固定size”提前确定好“该阶段que的长度”。
4：for()内遍历中，注意要每次que推出首节点后，再用vec记录阶段node，que始终“领先”vec。

第一层while()：que中，处理第一层node(即root)，第一层node(即root)出去，第二层2个node进que。
第二层while()：que中，处理第二层2个node，第二层2个node出去，第3层4个node进que。其中for()内分2段。
...

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> result;
        if (root == nullptr) return result;
        queue<TreeNode*> que;
        que.push(root); // wyh 1
        while (!que.empty()) {
            vector<int> vec; // wyh 2
            int size = que.size(); // wyh 3
            for (int i = 0; i < size; i++) {
                auto node = que.front();
                que.pop(); // wyh 4
                vec.push_back(node->val);
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
            }
            result.push_back(vec);
        }
        return result;
    }
};

// 复习
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        // vec_all用来每轮while（即每层阶段性）结果vec。每轮while严格来说，对应的是（1-2层树，2-3层树...想3层树即可）
        vector<vector<int>> vec_all;
        // 二叉树问题，开局要想到root节点的判空情况
        if (root == nullptr) return vec_all; 
        // 队列que，用来处理层序遍历时，每层node的“进进出出”。在第1轮while之前，que会push第1层树root；
        // 在第1轮while时，通过内部for循环，que会pop第1层树root，会push第2层树的二个节点（想象一颗3层的完整树）；
        // 在第2轮while时，通过内部for循环，que会pop第2层树的二个节点，会push第3层树的四个节点；
        // ...
        queue<TreeNode*> que; 
        // 在第1轮while之前，que会push第1层树root
        que.push(root);
        // 在第3轮while时，通过内部for循环，que会pop出第3层树的四个节点，而不会push任何节点再进入que（因为走到头了）
        // 因此在第4轮while时，会退出
        // 第1轮while----涉及1~2层树，第2轮while----涉及2-3层树
        while (!que.empty()) {
            // 每轮while进来，都重新创建vec，因为vec存的是每层阶段性结果，在每轮while结束前，给到vec_all
            vector<int> vec;
            // 第1轮while，que.size是1（que里有第1层树1个root）；
            // 第2轮while，que.size是2（que里有第2层树二个节点）
            int size = que.size();
            // que.size的值，决定内部for循环的次数
            for (int i = 0; i < size; i++) {
                // 以下3步是固定顺序，先取pop的front节点，然后pop剔除，然后装入vec
                // que.size有几个，就会通过内部for循环，pop剔除几次
                TreeNode* node = que.front();
                // 第1轮while，que会pop第1层树root
                // 第2轮while，que会pop第2层树的二个节点；...
                que.pop();
                // 第1轮while，vec存的是第1层树的root；
                // 第2轮while，vec存的是第2层树的二个节点；...
                vec.push_back(node->val);
                // 第1轮while，que会push第2层树的二个节点；
                // 第2轮while，que会push第2层树的四个节点；
                // 第2轮while，以下判断为空，跳过不push
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
                // 简单说就是，推出1个推进2个，推出2个推进4个，推出4个推进0个
                // 推出的计数，和vec装结果的计数一致，即推出1个，装第1层树的1个结果，推出2个，装第2层树的2个结果
            }
            // 第1轮while，vec_all累加的是：vec存的是第1层树的root；
            // 第2轮while，vec_all累加的是：vec存的是第2层树的二个节点；...
            vec_all.push_back(vec);
        }
        return vec_all;
    }
};