LeetCode102.二叉树的层序遍历（按层输出和统一输出）

LeetCode102.二叉树的层序遍历

1.问题

2.思路

（1）什么是层次遍历

按照层数由小到大，同层由左向右的次序访问结点

实现：（需借助队列！）

在第i层上若结点x在结点y的左边，则x一定在y之前被访问。并且，在第i+1层上，x的子节点一定在y的子节点之前被访问。

（2）借助队列执行

运行实例：

3.代码实现

按层输出，就是上图中按[[A] [BC] [DEF]]的格式输出。
统一输出，就是[ABCDEF]的格式。

a.按层输出版

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*> que;
        if (root != NULL) que.push(root);
        vector<vector<int>> result;
        while (!que.empty()) {
            int size = que.size();
            vector<int> vec;
            // 这里一定要使用固定大小size，不要使用que.size()，因为que.size是不断变化的
            for (int i = 0; i < size; i++) {//size表示按层序遍历 因为每次队列里都只留了一层的数据 
                TreeNode* node = que.front();
                que.pop();
                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;
    }
};

b.统一输出版

上面的代码改一下就可以

//这样可以输出层序遍历序列，但是不能按层输出。 
 class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*> que;
        if (root != NULL) que.push(root);
        vector<vector<int>> result;
        vector<int> vec;
        while (!que.empty()) {
            //int size = que.size();//把关于层次的去掉就可以
            //for (int i = 0; i < size; i++) {
                TreeNode* node = que.front();
                que.pop();
                vec.push_back(node->val);
                if (node->left) que.push(node->left);
                //result.push_back(vec);
                if (node->right) que.push(node->right);
            //}
        }
         result.push_back(vec);
        return result;
    }
};