C++力扣题目-- 二叉树层序遍历

• 102.二叉树的层序遍历(opens new window)
• 107.二叉树的层次遍历II(opens new window)
• 199.二叉树的右视图(opens new window)
• 637.二叉树的层平均值(opens new window)
• 429.N叉树的层序遍历(opens new window)
• 515.在每个树行中找最大值(opens new window)
• 116.填充每个节点的下一个右侧节点指针(opens new window)
• 117.填充每个节点的下一个右侧节点指针II(opens new window)
• 104.二叉树的最大深度(opens new window)
• 111.二叉树的最小深度

102思路：

我们之前讲过了三篇关于二叉树的深度优先遍历的文章：

• 二叉树：前中后序递归法(opens new window)
• 二叉树：前中后序迭代法(opens new window)
• 二叉树：前中后序迭代方式统一写法(opens new window)

接下来我们再来介绍二叉树的另一种遍历方式：层序遍历。

层序遍历一个二叉树。就是从左到右一层一层的去遍历二叉树。这种遍历的方式和我们之前讲过的都不太一样。

需要借用一个辅助数据结构即队列来实现，队列先进先出，符合一层一层遍历的逻辑，而用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。

而这种层序遍历方式就是图论中的广度优先遍历，只不过我们应用在二叉树上。

使用队列实现二叉树广度优先遍历，动画如下：

这样就实现了层序从左到右遍历二叉树。

代码如下：这份代码也可以作为二叉树层序遍历的模板，打十个就靠它了。

c++代码如下：

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;
    }
};

?

107--将102的结果reverse即可；

C++代码：

class Solution {
public:
    vector<vector<int>> levelOrderBottom(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;
            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);
        }
        reverse(result.begin(), result.end()); // 在这里反转一下数组即可
        return result;

    }
};

199--二叉树的右视图

层序遍历的时候，判断是否遍历到单层的最后面的元素，如果是，就放进result数组中，随后返回result就可以了。

C++代码：

class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
         vector<int>result;
         queue<TreeNode*>que;
         if (root != nullptr) { que.push(root); }
         while (!que.empty())
         {
             int size = que.size();
             for (int i = 0; i < size; i++)
             {
                TreeNode* cur = que.front();
                que.pop();
                if (i == size - 1) { result.push_back(cur->val); }
                if (cur->left) { que.push(cur->left); }
                if (cur->right) { que.push(cur->right); }
             }
         }
         return result;
    }
};

637--二叉树的层平均值

本题就是层序遍历的时候把一层求个总和在取一个均值。

C++代码:

class Solution {
public:
    vector<double> averageOfLevels(TreeNode* root) {
        queue<TreeNode*>que;
         vector<double>result;
         if (root != nullptr) { que.push(root); }
         while (!que.empty())
         {            
             int size = que.size();
             double sum = 0;
             for (int i = 0; i < size; i++)
             {
                 TreeNode* cur = que.front();
                 que.pop();
                 sum += cur->val;
                 if (cur->left) { que.push(cur->left); }
                 if (cur->right) { que.push(cur->right); }
             }
             sum /= size;
             result.push_back(sum);
         }
         return result;
    }
};

429. N 叉树的层序遍历

这道题依旧是模板题，只不过一个节点有多个孩子了

C++代码:

class Solution {
public:
    vector<vector<int>> levelOrder(Node* root) {
        queue<Node*>que;
         vector<vector<int>>result;
         if (root != nullptr) { que.push(root); }
         while (!que.empty())
         {
             int size = que.size();
             vector<int>tmp;
             for (int i = 0; i < size; i++)
             {
                 Node* cur = que.front();
                 tmp.push_back(cur->val);
                 que.pop();
                 int vsize = cur->children.size();
                 for(int j=0;j<vsize;j++)
                 {
                    if (cur->children[j]) {que.push(cur->children[j]);}
                 }
             }
             result.push_back(tmp);
         }
         return result;
    }
};

515.在每个树行中找最大值

层序遍历，取每一层的最大值

C++代码：

class Solution {
public:
    vector<int> largestValues(TreeNode* root) {
        queue<TreeNode*>que;
         vector<int>result;
         if (root != nullptr) 
         { 
             que.push(root); 
         }
         while (!que.empty())
         {
             int max = que.front()->val;
             int size = que.size();           
             for (int i = 0; i < size; i++)
             {
                 TreeNode* cur = que.front();
                 if (max < (cur->val)) { max = cur->val; }
                 que.pop();
                 if (cur->left) { que.push(cur->left); }
                 if (cur->right) { que.push(cur->right); }
             }
             result.push_back(max);
         }
         return result;
    }
};

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

思路

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

C++代码：

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

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

思路

这道题目说是二叉树，但116题目说是完整二叉树，其实没有任何差别，一样的代码一样的逻辑一样的味道

C++代码：

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

104.二叉树的最大深度

思路

使用迭代法的话，使用层序遍历是最为合适的，因为最大的深度就是二叉树的层数，和层序遍历的方式极其吻合。

在二叉树中，一层一层的来遍历二叉树，记录一下遍历的层数就是二叉树的深度，如图所示：

所以这道题的迭代法就是一道模板题，可以使用二叉树层序遍历的模板来解决的。

C++代码如下:

class Solution {
public:
    int maxDepth(TreeNode* root) {
        queue<TreeNode*>que;
         int depth = 0;
         if (root != nullptr) 
         {
            que.push(root);
         }
         while (!que.empty())
         {
             int size = que.size();
             for (int i = 0; i < size; i++)
             {
                 TreeNode* cur = que.front();
                 que.pop();
                 if (cur->left) { que.push(cur->left); }
                 if (cur->right) { que.push(cur->right); }
             }
             depth++;
         }
         return depth;
    }
};

111.二叉树的最小深度

思路

相对于 104.二叉树的最大深度 ，本题还也可以使用层序遍历的方式来解决，思路是一样的。

需要注意的是，只有当左右孩子都为空的时候，才说明遍历的最低点了。如果其中一个孩子为空则不是最低点

代码如下：（详细注释）

class Solution {
public:
    int minDepth(TreeNode* root) {
        queue<TreeNode*>que;
         int depth = 0;
         if (root != nullptr){que.push(root);}
         else {return depth;}                           
         while (!que.empty())
         {
             int size = que.size();
             depth++;
             for (int i = 0; i < size; i++)
             {
                 TreeNode* cur = que.front();
                 que.pop();
                 if (cur->left) { que.push(cur->left); }
                 if (cur->right) { que.push(cur->right); }
                 if (cur->left == nullptr && cur->right == nullptr)
                 {
                     return depth;
                 }
             }             
         }
         return depth;
    }
};