目录
①力扣429. N 叉树的层序遍历
难度 中等
给定一个 N 叉树,返回其节点值的层序遍历。(即从左到右,逐层遍历)。
树的序列化输入是用层序遍历,每组子节点都由 null 值分隔(参见示例)。
示例 1:
输入:root = [1,null,3,2,4,null,5,6] 输出:[[1],[3,2,4],[5,6]]
示例 2:
输入:root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14] 输出:[[1],[2,3,4,5],[6,7,8,9,10],[11,12,13],[14]]
提示:
- 树的高度不会超过
1000
- 树的节点总数在
[0, 10^4]
之间
/*
// Definition for a Node.
class Node {
public:
int val;
vector<Node*> children;
Node() {}
Node(int _val) {
val = _val;
}
Node(int _val, vector<Node*> _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
public:
vector<vector<int>> levelOrder(Node* root) {
}
};
解析代码
层序遍历即可,仅需多加一个变量,用来记录每一层结点的个数。
- ① 让根节点先入队。
- ② 记录当前队头后打印,并让队头出队,然后检测,如果孩子不为空就把孩子带进去。(上一层节点出队时带入下一层节点入队)
- ③ 只要队列不为空就说明还没完。如果队列为空,说明下面最后一层没有节点,遍历结束。
/*
// Definition for a Node.
class Node {
public:
int val;
vector<Node*> children;
Node() {}
Node(int _val) {
val = _val;
}
Node(int _val, vector<Node*> _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
public:
vector<vector<int>> levelOrder(Node* root) {
vector<vector<int>> ret;
if(root == nullptr)
return ret;
queue<Node*> q;
q.push(root);
while(!q.empty())
{
int sz = q.size();
vector<int> tmp(sz); // 统计本层结点
for(int i = 0; i < sz; ++i)
{
Node* t = q.front();
q.pop();
tmp[i] = t->val;
for(auto& child : t->children) // 遍历下层孩子结点入队
{
if(child != nullptr)
q.push(child);
}
}
ret.push_back(tmp);
}
return ret;
}
};
②力扣103. 二叉树的锯齿形层序遍历
难度 中等
给你二叉树的根节点 root
,返回其节点值的 锯齿形层序遍历 。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。
示例 1:
输入:root = [3,9,20,null,null,15,7] 输出:[[3],[20,9],[15,7]]
示例 2:
输入:root = [1] 输出:[[1]]
示例 3:
输入:root = [] 输出:[]
提示:
- 树中节点数目在范围
[0, 2000]
内 -100 <= Node.val <= 100
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
}
};
解析代码
在正常的层序遍历过程中,我们是可以把一层的结点放在一个数组中去的。 既然我们有这个数组,在合适的层数逆序就可以得到锯齿形层序遍历的结果,可以弄一个int level遍历,偶数层的时候逆序,也可以用一个bool flag标志,一层修改一次,这里用标志的写法:
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
vector<vector<int>> ret;
if(root == nullptr)
return ret;
queue<TreeNode*> q;
q.push(root);
bool flag = false;
while(!q.empty())
{
int sz = q.size();
vector<int> tmp(sz); // 统计本层结点
for(int i = 0; i < sz; ++i)
{
TreeNode* t = q.front();
q.pop();
tmp[i] = t->val;
// 下层孩子结点入队
if(t->left != nullptr)
q.push(t->left);
if(t->right != nullptr)
q.push(t->right);
}
if(flag)
reverse(tmp.begin(), tmp.end());
ret.push_back(tmp);
flag = flag == false ? true : false;
}
return ret;
}
};
③力扣662. 二叉树最大宽度
难度 中等
给你一棵二叉树的根节点 root
,返回树的 最大宽度 。
树的 最大宽度 是所有层中最大的 宽度 。
每一层的 宽度 被定义为该层最左和最右的非空节点(即,两个端点)之间的长度。将这个二叉树视作与满二叉树结构相同,两端点间会出现一些延伸到这一层的 null
节点,这些 null
节点也计入长度。
题目数据保证答案将会在 32 位 带符号整数范围内。
示例 1:
输入:root = [1,3,2,5,3,null,9] 输出:4 解释:最大宽度出现在树的第 3 层,宽度为 4 (5,3,null,9) 。
示例 2:
输入:root = [1,3,2,5,null,null,9,6,null,7] 输出:7 解释:最大宽度出现在树的第 4 层,宽度为 7 (6,null,null,null,null,null,7) 。
示例 3:
输入:root = [1,3,2,5] 输出:2 解释:最大宽度出现在树的第 2 层,宽度为 2 (3,2) 。
提示:
- 树中节点的数目范围是
[1, 3000]
-100 <= Node.val <= 100
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int widthOfBinaryTree(TreeNode* root) {
}
};
解析代码
第一种思路(会超过内存限制): 既然统计每一层的最大宽度,我们优先想到的就是利用序遍历,把当前层的结点全部存在队列里面,利用队列的长度来计算每一层的宽度,统计出最大的宽度。 但是由于空节点也是需要计算在内的。因此可以选择将空节点也存在队列里面。 这个思路是我们正常会想到的思路,但是极端境况下,最左边一条长链,最右边一条长链,需要存几亿个空节点,会超过最大内存限制。
第二种思路(利用二叉树的顺序存储 - 通过根节点的下标,计算左右孩子的下标):
依旧是利用层序遍历,但是这一次队列里面不单单存结点信息,并且还存储当前结点如果在数组中存储所对应的下标(学习数据结构:堆的时候,学过计算左右孩子的方式)。
这样我们计算每一层宽度的时候,无需考虑空节点,只需将当层结点的左右结点的下标相减再加 1 即可,因为要用左右结点,所以可以考虑用vector数组模拟queue队列。
但是这里有个细节问题:如果二叉树的层数非常恐怖的话,任何一种数据类型都不能存下下标的值。但是没有问题,因为数据的存储是一个环形的结构。并且题目说明,数据的范围在 int 这个类型的最大值的范围之内,因此不会超出一圈。因此,如果是求差值的话,我们无需考虑溢出的情况。(用unsigned int即可)
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int widthOfBinaryTree(TreeNode* root) {
vector<pair<TreeNode*, unsigned int>> q; // ⽤数组模拟队列,结点+下标
q.push_back({root, 0}); // 数组右边进,左边出
unsigned int ret = 0;
while(!q.empty())
{
// 先更新这⼀层的宽度
auto& [x1, y1] = q[0];
auto& [x2, y2] = q.back();
ret = max(ret, y2 - y1 + 1);
vector<pair<TreeNode*, unsigned int>> tmp; // 下层非空结点入队,直接替换即可
for(auto& [x, y] : q) // 获取 结点+下标
{
if(x->left != nullptr)
tmp.push_back({x->left, y * 2 + 1});
if(x->right != nullptr)
tmp.push_back({x->right, y * 2 + 2});
}
q = tmp;
}
return ret;
}
};
④力扣515. 在每个树行中找最大值
难度 中等
给定一棵二叉树的根节点 root
,请找出该二叉树中每一层的最大值。
示例1:
输入: root = [1,3,2,5,3,null,9] 输出: [1,3,9]
示例2:
输入: root = [1,2,3] 输出: [1,3]
提示:
- 二叉树的节点个数的范围是
[0,10^4]
-2^31 <= Node.val <= 2^31 - 1
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int> largestValues(TreeNode* root) {
}
};
解析代码
层序遍历过程中,在执行让下一层节点入队的时候,我们是可以在循环中统计出当前层结点的最大值的。 因此可以在 bfs 的过程中,统计出每一层结点的最大值。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int> largestValues(TreeNode* root) {
vector<int> ret;
if(root == nullptr)
return ret;
queue<TreeNode*> q;
q.push(root);
while(!q.empty())
{
int sz = q.size(), maxVal = INT_MIN;
while(sz--)
{
TreeNode* t = q.front();
maxVal = max(maxVal, t->val);
q.pop();
if(t->left)
q.push(t->left);
if(t->right)
q.push(t->right);
}
ret.push_back(maxVal);
}
return ret;
}
};
本篇完。
下一篇动态规划类型的是回文串dp类型的OJ。
下下篇是优先级队列_堆类型的OJ。
标签:right,TreeNode,val,Offer,int,由易到难,nullptr,20,left From: https://blog.csdn.net/GRrtx/article/details/136615326