代码随想录刷题Day33

这次刷题的主题依旧是关于树的层级遍历问题。

在每个树行中找最大值

这道题套用树的层序遍历模板，每一层中找出每一层的最大值。代码如下：

class Solution {
public:
    vector<int> largestValues(TreeNode* root) {
        queue<TreeNode*> levelQueue;
        vector<int> ans;
        TreeNode* tmp;
        int cnt = 0;
        int max = -214748347;

        //空树
        if(!root) return ans;

        levelQueue.push(root);//第一次写代码把这一行代码漏掉，结果导致返回的都是空列表

        while(!levelQueue.empty()){
            cnt = levelQueue.size();
            max = -2147483648;
            while(cnt--){   //每一层节点取出
                tmp = levelQueue.front();
                levelQueue.pop();

                if(tmp->val > max) max = tmp->val;  //值和当前的最大值比较

                if(tmp->left) levelQueue.push(tmp->left);   //下一层节点入队
                if(tmp->right) levelQueue.push(tmp->right);

            }
            ans.push_back(max);
        }
        return ans;

    }
};

填充每个节点的下一个右侧节点指针

这道题是在树的纵向结构的基础上，添加横向的指针连接起来，如果想到使用层级遍历的话，这道题思路可以很快有。填充每个节点的下一个右侧节点指针II这道题也可以使用树的层级遍历方法求解：

class Solution {
public:
    Node* connect(Node* root) {
        queue<Node*> levelQueue;
        if(!root) return root;
        levelQueue.push(root);
        int cnt = 1;
        Node* tmp;
        while(!levelQueue.empty()){
            cnt = levelQueue.size();
            while(cnt--){
                tmp = levelQueue.front();
                levelQueue.pop();
                if(tmp->left) levelQueue.push(tmp->left);
                if(tmp->right) levelQueue.push(tmp->right);
                if(cnt > 0){
                    tmp->next = levelQueue.front(); //为每一层的非最后一个节点指定next节点
                }
            }
        }
        return root;
    }
};

二叉树的最大深度

这道求树的深度，可以是用深度优先搜索，也可以用广度优先搜索，既然这是在树的层序遍历系列题目下，这里就使用树的层序遍历，在逐层遍历的同时，对遍历了多少层进行一个计数：

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(!root) return 0;
        queue<TreeNode*> levelQueue;
        levelQueue.push(root);
        int queue_cnt = 1;
        int level_cnt = 0;
        TreeNode* tmp ;
        while(!levelQueue.empty()){
            level_cnt++;
            queue_cnt = levelQueue.size();
            while(queue_cnt--){
                tmp = levelQueue.front();
                levelQueue.pop();
                if(tmp->left) levelQueue.push(tmp->left);
                if(tmp->right) levelQueue.push(tmp->right);
            }
        }
        return level_cnt;
    }
};

二叉树的最小深度

这道题继续使用层级遍历的方法，逐层遍历树，直到在某一层遇到第一个叶子节点就停止继续遍历，其中叶子节点的特点是左孩子和右孩子均为空。代码如下：

class Solution {
public:
    int minDepth(TreeNode* root) {

        if(!root) return 0;

        queue<TreeNode*> levelQueue;

        int queue_cnt = 1;
        int min_level_cnt = 0;
        bool min_find = false;

        levelQueue.push(root);

        TreeNode* tmp;

        while(!levelQueue.empty()){

            queue_cnt = levelQueue.size();
            min_level_cnt ++;   //下一层的节点遍历

            while(queue_cnt --){//挨个取这一层的节点

                tmp = levelQueue.front();
                levelQueue.pop();

                if(!tmp->left && !tmp->right){
                    //在这一层遇到一个叶子节点，即可结束遍历过程
                    min_find = true;
                    break;
                }

                else{//如果没有叶子节点，则继续把下一层节点入队
                    if(tmp->left) levelQueue.push(tmp->left);
                    if(tmp->right) levelQueue.push(tmp->right);
                }
            }
            if(min_find) break; //找到叶子节点，无需继续遍历下去
        }
        return min_level_cnt;
    }
};

层序遍历小结

对于使用这一类解法，典型的特点是处理的内容和每一层有很强的关联，比如

• 直接求层序遍历结果
• 或者是求每一层的相关属性，如求右视图是在求每一层的最右节点，求每一层的平均值，或者是最大值，或者是在每一层中添加横向的next指针
• 或者是关于树深度的一些性质，由于树的层序遍历时一层一层的遍历，所以，树的深度也是可以在一层层扫描中获得。

整体写代码的思路框架是：

• root是否为空指针的判断（这几乎成为大部分处理树的问题的第一步操作）
• 如果root非空
  • 外层循环用于逐层遍历。使用一个队列levelQueue记录每一层的节点，cnt在每一层的节点遍历之前记下队列中元素的个数，也是这一层的节点数目，用于控制队列元素出队的次数
    • 外层循环可以用于处理比如关于深度计算的问题。
  • 内层循环用于每一层中的元素遍历。从队列中依次出队cnt个元素，并把这cnt个元素的left（如果非空）和rigth（如果非空）加入队列，作为下一层要遍历的元素。
    • 在这一个内层循环里，可以执行关于树的层级相关操作，比如print元素（层序遍历结果的返回）、计算平均值、求最大值、求最右节点、层内结点横向连接等。
  • 如此执行外层循环，直到队列为空，也就是下一层没有元素要遍历为止。
• 最后返回满足要求的答案值。