LeetCode 102 二叉树的层序遍历

102.二叉树的层序遍历

1.1 基于队列实现层序遍历

在下面的实现方式中存在一种好处，就是可以在程序判断当前所处的层数。

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        deque<TreeNode*> dq;
        vector<vector<int>> ans;
        if(!root) return ans;
        dq.push_back(root);
        TreeNode *pre=root,*end;
        vector<int> level;
        while(!dq.empty()){
            root=dq.front();
            dq.pop_front();
            level.push_back(root->val);
            if(root->left){
                dq.push_back(root->left);
                end=root->left;
            }
            if(root->right){
                dq.push_back(root->right);
                end=root->right;
            }
            if(root==pre){
                pre=end;
                ans.push_back(level);
                level.clear();
            }
        }
        return ans; 
    }
};

另一种实现方式,直接按照层进行循环,在while循环内部添加一个for循环，每次for循环直接处理完一层的元素。（层的控制上一层中元素个数来实现，上一层中n个元素，这一层就循环n次）或者从另外一个角度去理解，在上一层中已经将当前层的元素加入到了队列中，那么保存队列的元素个数，对当前层进行处理即可。

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++) {
                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;
    }
};