目录
1. N 叉树的层序遍历(中等)
2. 二叉树的锯齿形层序遍历(中等)
3. 二叉树的最大宽度(中等)
4. 在每个树行中找最大值(中等)
5. 找树左下角的值(中等)
6. 二叉树的右视图(中等)
1. N 叉树的层序遍历(中等)
先让根结点root入队,队列中:①
第一层遍历:让①出队,让①的孩子③②④入队,队列中:①③②④
第二层遍历:让③②④出队,让③的孩子⑤⑥入队(②④没有孩子),队列中:③②④⑤⑥
第三层遍历:让⑤⑥出队,⑤⑥没孩子。
队列为空,层序遍历结束。
代码流程设计:先让根节点入队。然后在每一轮层序遍历中,计算当前队列中节点的个数(即本层节点的个数),记为count,依次让count个节点出队,把本层节点的值放到临时数组中,并让本层节点的孩子(即下一层节点)入队。该轮层序遍历完成后,把临时数组添加到答案中。
class Solution {
public:
vector<vector<int>> levelOrder(Node* root) {
if (root == nullptr)
return {};
vector<vector<int>> ans;
queue<Node*> q;
q.push(root);
while (!q.empty())
{
int count = q.size(); // 本层节点的个数
vector<int> tmp; // 记录本层节点的值
for (int i = 0; i < count; i++)
{
// 本层节点出队
Node* cur = q.front();
q.pop();
// 把本层节点的值放入临时数组中
tmp.push_back(cur->val);
// 本层节点的孩子(下一层节点)入队
for (auto& child : cur->children)
{
if (child != nullptr)
{
q.push(child);
}
}
}
ans.push_back(tmp);
}
return ans;
}
};
2. 二叉树的锯齿形层序遍历(中等)
创建一个变量level表示层数,假设二叉树从第1层开始。level为奇数,正序遍历;level为偶数,逆序遍历。
class Solution {
public:
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
if (root == nullptr)
return {};
vector<vector<int>> ans;
queue<TreeNode*> q;
q.push(root);
int level = 1;
while (!q.empty())
{
int count = q.size(); // 本层节点的个数
vector<int> tmp; // 记录本层节点的值
for (int i = 0; i < count; i++)
{
// 本层节点出队
TreeNode* cur = q.front();
q.pop();
// 把本层节点的值放入临时数组中
tmp.push_back(cur->val);
// 本层节点的孩子(下一层节点)入队
if (cur->left)
{
q.push(cur->left);
}
if (cur->right)
{
q.push(cur->right);
}
}
// 如果本层是偶数层,将临时数组反转,再放入答案中
if (level % 2 == 0)
{
reverse(tmp.begin(), tmp.end());
}
ans.push_back(tmp);
level++;
}
return ans;
}
};
3. 二叉树的最大宽度(中等)
利用二叉树的顺序存储方式给二叉树的节点编号,假设根结点编号为1,编号为x的节点的两个孩子的编号分别为2x和2x+1。让节点和编号一起入队,每层宽度 = 队尾编号 - 队头编号 + 1。
代码流程设计:先让根节点入队。然后在每一轮层序遍历中,计算本层宽度并更新答案,计算当前队列中节点的个数(即本层节点的个数),记为count,依次让count个节点出队,并让本层节点的孩子(即下一层节点)入队。
如果二叉树的层数非常非常非常多时,任何一种数据类型都存不下编号。因为无符号整型溢出时会自动取模,而且题目数据保证答案将会在32位带符号整数范围内,所以用unsigned int存储编号就可以保证答案正确。
class Solution {
public:
int widthOfBinaryTree(TreeNode* root) {
unsigned int ans = 0;
queue<pair<TreeNode*, unsigned int>> q;
q.push({ root,1 });
while (!q.empty())
{
unsigned int width = q.back().second - q.front().second + 1; // 本层宽度
ans = max(ans, width);
int count = q.size(); // 本层节点的个数
for (int i = 0; i < count; i++)
{
// 本层节点出队
TreeNode* cur = q.front().first;
unsigned int num = q.front().second; // cur的编号
q.pop();
// 本层节点的孩子(下一层节点)入队
if (cur->left)
{
q.push({ cur->left,2 * num });
}
if (cur->right)
{
q.push({ cur->right,2 * num + 1 });
}
}
}
return ans;
}
};
4. 在每个树行中找最大值(中等)
层序遍历的过程中找最大值。
class Solution {
public:
vector<int> largestValues(TreeNode* root) {
if (root == nullptr)
return {};
vector<int> ans;
queue<TreeNode*> q;
q.push(root);
while (!q.empty())
{
int count = q.size(); // 本层节点的个数
int tmp = INT_MIN;
for (int i = 0; i < count; i++)
{
// 本层节点出队
TreeNode* cur = q.front();
q.pop();
// 更新tmp
tmp = max(tmp, cur->val);
// 本层节点的孩子(下一层节点)入队
if (cur->left)
{
q.push(cur->left);
}
if (cur->right)
{
q.push(cur->right);
}
}
ans.push_back(tmp);
}
return ans;
}
};
5. 找树左下角的值(中等)
层序遍历的过程中找最左边的值。
class Solution {
public:
int findBottomLeftValue(TreeNode* root) {
if (root == nullptr)
return {};
int ans = 0;
queue<TreeNode*> q;
q.push(root);
while (!q.empty())
{
int count = q.size(); // 本层节点的个数
for (int i = 0; i < count; i++)
{
// 本层节点出队
TreeNode* cur = q.front();
q.pop();
// 如果遍历到本层最左边的节点,更新ans
if (i == 0)
{
ans = cur->val;
}
// 本层节点的孩子(下一层节点)入队
if (cur->left)
{
q.push(cur->left);
}
if (cur->right)
{
q.push(cur->right);
}
}
}
return ans;
}
};
6. 二叉树的右视图(中等)
层序遍历的过程中找最右边的值。
class Solution {
public:
vector<int> rightSideView(TreeNode* root) {
if (root == nullptr)
return {};
vector<int> ans;
queue<TreeNode*> q;
q.push(root);
while (!q.empty())
{
int count = q.size(); // 本层节点的个数
for (int i = 0; i < count; i++)
{
// 本层节点出队
TreeNode* cur = q.front();
q.pop();
// 如果遍历到本层最右边的节点,将值添加到答案
if (i == count - 1)
{
ans.push_back(cur->val);
}
// 本层节点的孩子(下一层节点)入队
if (cur->left)
{
q.push(cur->left);
}
if (cur->right)
{
q.push(cur->right);
}
}
}
return ans;
}
};