今日题目

题目	难度	备注
102. 二叉树的层序遍历	中等	一招鲜吃遍天
107. 二叉树的层序遍历 II ）	中等
199. 二叉树的右视图	中等
637. 二叉树的层平均值	简单
429. N 叉树的层序遍历	中等
515. 在每个树行中找最大值	中等
116. 填充每个节点的下一个右侧节点指针	中等
104. 二叉树的最大深度	简单
111. 二叉树的最小深度	简单

题目：102. 二叉树的层序遍历

102. 二叉树的层序遍历 - 力扣（LeetCode）

一、源代码

class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int> > ans;if(root == nullptr){return ans;}queue<TreeNode*> q;q.push(root);while (!q.empty()) {                                    //层次遍历队列int n = q.size();vector<int> layer;while(n--) {                                       // 遍历每一层，将遍历的元素出队，并将下一层压入队列TreeNode* now = q.front();q.pop();layer.push_back(now->val);                     //存储每一层的结点值if (now->left) q.push(now->left);if (now->right) q.push(now->right);}ans.push_back(layer);layer.clear();}return ans;}
};

二、代码思路

利用 queue<TreeNode*> q 实现树的层次遍历。在遍历队列的过程中，利用while(q.size()–) 实现遍历每一层，将遍历的元素出队，并将下一层压入队列，最后就得到了各层结点值了。

---

题目：107. 二叉树的层序遍历 II

107. 二叉树的层序遍历 II - 力扣（LeetCode）

一、源代码

class Solution {
public:vector<vector<int>> levelOrderBottom(TreeNode* root) {vector<vector<int>> ans;if (root == nullptr) {return ans;}queue<TreeNode*> q;q.push(root);while (!q.empty()) {                        // 层次遍历队列int n = q.size();vector<int> layer;while (n--) {                           // 遍历每一层，将遍历的元素出队，并将下一层压入队列TreeNode* now = q.front();q.pop();layer.push_back(now->val);          // 存储每一层的结点值if (now->left)q.push(now->left);if (now->right)q.push(now->right);}ans.push_back(layer);layer.clear();}reverse(ans.begin(),ans.end());             //反转层次遍历，得到自底向上的层次遍历return ans;}
};

二、代码思路

反转层次遍历，得到自底向上的层次遍历。官方也这样做，那就心安理得，直接下一题了咯。

---

题目：199. 二叉树的右视图

199. 二叉树的右视图 - 力扣（LeetCode）

一、源代码

class Solution {
public:vector<int> rightSideView(TreeNode* root) {vector<int> ans;if (root == nullptr) {return ans;}queue<TreeNode*> q;q.push(root);while (!q.empty()) {                                 // 层次遍历队列int n = q.size();while (n--) {                                    // 遍历每一层，将遍历的元素出队，并将下一层压入队列TreeNode* now = q.front();q.pop();if(n == 0)  ans.push_back(now->val);         // 将每层最后一个结点压入ans数组中if (now->left)  q.push(now->left);if (now->right) q.push(now->right);}}return ans;}
};

二、代码思路

层次遍历队列，将每层最后一个结点压入ans数组中（此时 n == 0）。

---

题目：637. 二叉树的层平均值

637. 二叉树的层平均值 - 力扣（LeetCode）

一、源代码

class Solution {
public:vector<int> rightSideView(TreeNode* root) {vector<double> ans;if (root == nullptr) {return ans;}queue<TreeNode*> q;q.push(root);while (!q.empty()) {                                  // 层次遍历队列int cnt = q.size(), n = cnt;double sum = 0;while (cnt--) {                                   // 遍历每一层，将遍历的元素出队，并将下一层压入队列TreeNode* now = q.front();q.pop();sum += now->val;                              // 统计每层结点值之和if (now->left)  q.push(now->left);if (now->right) q.push(now->right);}ans.push_back(sum / n);                           // 计算平均值并存入 ans 数组}return ans;}
};

二、代码思路

层次遍历队列，统计每层结点值之和，最后计算平均值并存入 ans数组。

---

题目：429. N 叉树的层序遍历

429. N 叉树的层序遍历 - 力扣（LeetCode）

一、源代码

class Solution {
public:vector<vector<int>> levelOrder(Node* root) {vector<vector<int>> ans;if (root == nullptr) {return ans;}queue<Node*> q;q.push(root);while (!q.empty()) {                           // 层次遍历队列int n = q.size();vector<int> layer;while (n--) {                             // 遍历每一层，将遍历的元素出队，并将下一层压入队列Node* now = q.front();q.pop();layer.push_back(now->val);            // 存储每一层的结点值for (int i = 0; i < now->children.size(); i++) {q.push(now->children[i]);}}ans.push_back(layer);layer.clear();}return ans;}
};

二、代码思路

利用 queue<Node*> q 实现树的层次遍历。在遍历队列的过程中，利用while(q.size()–) 实现遍历每一层，将遍历的元素出队，并将下一层压入队列，最后就得到了各层结点值了。

---

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

515. 在每个树行中找最大值 - 力扣（LeetCode）

一、源代码

class Solution {
public:vector<int> largestValues(TreeNode* root) {vector<int> ans;if (root == nullptr) {return ans;}queue<TreeNode*> q;q.push(root);while (!q.empty()) {                       // 层次遍历队列int cnt = q.size(), n = cnt;int maxVal = INT_MIN;while (cnt--) {                      // 遍历每一层，将遍历的元素出队，并将下一层压入队列TreeNode* now = q.front();q.pop();if (now->val > maxVal) maxVal = now->val;if (now->left)  q.push(now->left);if (now->right) q.push(now->right);}ans.push_back(maxVal);}return ans;}
};

---

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

116. 填充每个节点的下一个右侧节点指针 - 力扣（LeetCode）

一、源代码

class Solution {
public:Node* connect(Node* root) {if (root == nullptr) {return root;}queue<Node*> q;q.push(root);while (!q.empty()) {               // 层次遍历队列int cnt = q.size();while (cnt--) {                // 遍历每一层，将遍历的元素出队，并将下一层压入队列Node* now = q.front();q.pop();if (cnt > 0) {             // 连接now->next = q.front();}if (now->left)q.push(now->left);if (now->right)q.push(now->right);}}return root;}
};

二、代码思路

初始状态下，所有 next 指针都被设置为 NULL。所以只要层次遍历树，在每层中进行连接就行。

---

题目：104. 二叉树的最大深度

104. 二叉树的最大深度 - 力扣（LeetCode）

一、源代码

class Solution {
private:int DFS(TreeNode* root,int h) {if (!root) return h;int l = DFS(root->left,h+1);int r = DFS(root->right,h+1);return l > r ? l : r;}
public:int maxDepth(TreeNode* root) {return DFS(root,0);}
};

二、代码思路

利用递归，每次递归处理一层中的一个结点。对每一层的一个结点有两种情况：

① root 为空指针，则说明递归到底，返回 高度h 就行。

② root 不为空，则找它的左右孩子的高度，并返回较大的高度 h。

对树顶点开始执行递归就得到了最大高度。

---

题目：111. 二叉树的最小深度

111. 二叉树的最小深度 - 力扣（LeetCode）

一、源代码

class Solution {
private:int minH = INT_MAX;void DFS(TreeNode* root, int h) {if (!root)return ;if (!root->left && !root->right) {        // 遇到叶子结点则更新 minHminH = min(minH,h+1);}DFS(root->left,h+1);DFS(root->right,h+1);}public:int minDepth(TreeNode* root) {DFS(root,0);return root ? minH : 0;                  // 为空指针返回 0，否则返回 minH}
};

二、代码思路

DFS 遍历树，且每下一层高度 h+1，当访问到叶子结点时，就得出了一条从根节点到最近叶子结点的路径长度了（为当前h+1），记录最小的路径长度即为答案