二叉树的层次遍历系列

方法一：

class Solution {
public:
    vector> levelOrder(TreeNode* root) {
        if(!root) return {};
        vector > res;
        queue > q;
        int level = 0, lvl = 0;
        q.push(pair(root, level));

        TreeNode* cur;
        
        vector tmp;

        while(!q.empty()){    
            cur = q.front().first;
            lvl = q.front().second;
            q.pop();

            if(level + 1 == lvl){
                res.push_back(tmp);
                level++;
                tmp.clear();
            }  

            if(lvl == level)
                tmp.push_back(cur->val);
            

            if(cur->left){
                q.push(pair(cur->left, lvl + 1));
            }
            if(cur->right){
                q.push(pair(cur->right,  lvl+ 1));
            }

            if(q.empty() && tmp.size() != 0) res.push_back(tmp); 

        }

        return res;
    }
};

法二：

class Solution {
public:
    vector> levelOrder(TreeNode* root) {
        queue que;
        if (root != NULL) que.push(root);
        vector> result;
        while (!que.empty()) {
            int size = que.size();
            vector 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;
    }
};

class Solution {
public:
    vector> levelOrder(Node* root) {
        queue que;
        if (root != NULL) que.push(root);
        vector> result;
        while (!que.empty()) {
            int size = que.size();
            vector vec;
            // 这里一定要使用固定大小size，不要使用que.size()，因为que.size是不断变化的
            for (int i = 0; i < size; i++) {
                Node* node = que.front();
                que.pop();
                vec.push_back(node);
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
            }
            result.push_back(vec);
        }
        return result;
    }

    Node* connect(Node* root) {
        vector> lst = levelOrder(root);
        for(int i = 0; i < lst.size(); i++){
            int size = lst[i].size();
            for(int j = 0; j < size; j++){
                if(j == size - 1) lst[i][j]->next = NULL;
                else{
                    if(j + 1 < size)
                        lst[i][j]->next = lst[i][j+1]; 
                
                    
                }
            }
        }
        return root;
        
    }
};

本题依然是层序遍历，只不过在单层遍历的时候记录一下本层的头部节点，然后在遍历的时候让前一个节点指向本节点就可以了

class Solution {
public:
    Node* connect(Node* root) {
        queue que;
        if (root != NULL) que.push(root);
        
        while (!que.empty()) {
            int size = que.size();
            Node* prenode;
            
            for (int i = 0; i < size; i++) {
                
                Node* node = que.front();
                que.pop();
                if(i == 0){
                    prenode = node;
                }
                else{
                    prenode->next = node;
                }
                prenode = node;
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
            }
            
        }
        return root;
    }
};

二叉树的深度即层序遍历的层数（二叉树的层数），故使用层序遍历正适合

class Solution {
public:
    int maxDepth(TreeNode* root) {
        queue que;
        int depth = 0;
        if (root != NULL) que.push(root);
        
        while (!que.empty()) {
            int size = que.size();
            depth++;
            // 这里一定要使用固定大小size，不要使用que.size()，因为que.size是不断变化的
            for (int i = 0; i < size; i++) {
                //if(i == 0) depth++;
                TreeNode* node = que.front();
                que.pop();
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
            }
            
            
        }
        return depth;

    }
};

本题还也可以使用层序遍历的方式来解决，思路是一样的。
需要注意的是，只有当左右孩子都为空的时候(叶子结点)，才说明遍历的最低点了。如果其中一个孩子为空则不是最低点

class Solution {
public:
    int minDepth(TreeNode* root) {
        if (root == NULL) return 0;
        int depth = 0;
        queue que;
        que.push(root);
        while(!que.empty()) {
            int size = que.size();
            depth++; // 记录最小深度
            for (int i = 0; i < size; i++) {
                TreeNode* node = que.front();
                que.pop();
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
                if (!node->left && !node->right) { // 当左右孩子都为空的时候，说明是最低点的一层了，退出
                    return depth;
                }
            }
        }
        return depth;
    }
};