数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装设计
法学带有空值二叉树的最大宽度
二叉树定义为一种树形数据结构，其中每个节点最多有两个子节点。
二叉树某一层的宽度定义为该层最右节点和最左节点之间的节点数，包括中间的空节点。
二叉树的最大宽度定义为二叉树每一层宽度中的最大值。
在第一种方法中，我们将二叉树表示为堆数据结构的数组表示形式。每一层的宽度将是数组中最右子节点的索引与最左子节点的索引之差。之后，我们只需要找到这些宽度值中的最大值。
在第二种方法中，我们使用层序遍历，根据每个节点的父节点为其分配一个 ID。每一层的宽度将是该层最后一个节点的 ID 与第一个节点的 ID 之差。然后，我们可以将这些值的最大值作为答案。
问题陈述 - 给定一个包含 N 个节点的二叉树，我们需要找到带有空值的二叉树的最大宽度，其中最大宽度定义为每一层宽度中的最大值。
示例
输入
11
/ \
23 13
/ \ \
14 54 46
/ /
27 38
输出
4
解释
第一层的宽度为 1。
第二层的宽度为 2。
第三层的宽度为 4。
第四层的宽度为 3。
因此，最大宽度是所有这些值的 最大值 -
max{1,2,4,3} = 4.
输入
1
\
12
\
36
输出
1
解释
每一层的宽度都是 1。所以答案是 1。
输入
1
/ \
2 3
/ \
4 5
/ \
6 7
输出
8
解释
第一层的宽度是 1。
第二层的宽度为 2。
第三层的宽度为 4。
第四层的宽度是 8。
因此，最大宽度是 8。
方法 1
在这种方法中，我们将使用堆数据结构的数组形式来表示二叉树。如果存在索引为 i 的节点，则其子节点的索引将分别为 (2*i+1) 和 (2*i+2)。现在每一层的宽度由该层最右子节点的索引与最左子节点的索引之差给出。为了找到最大宽度，我们只需取所有这些宽度的最大值。
算法
步骤 1 - 创建树结构体 Tree。
步骤 1.1 - Tree 将包含一个整数 val 和两个指向自身的指针 left 和 right。
步骤 2 - 创建两个哈希映射 mx_ind 和 mn_ind，它们存储每一层极端节点（最左和最右）的位置。
步骤 3 - 设计并创建一个递归方法 fill_maps 来填充哈希映射。
步骤 3.1 - 如果根节点为 NULL，则返回。
步骤 3.2 - 将每一层的索引的最左值和最右值存储在 mn_ind 和 mx_ind 中
步骤 3.3 - 通过将级别更新为 level + 1，并将索引更新为 2*index + 1，递归调用节点的左子节点。
步骤 3.4 - 通过将级别更新为 level + 1，并将索引更新为 2*index + 2，递归调用节点的右子节点。
步骤 4 - 调用函数 fill_maps 来填充哈希映射。
步骤 5 - 遍历哈希映射，并返回 mx_ind[L] - mn_ind[L] + 1 的最大值。
示例
#include<iostream>
#include<map>
#include<algorithm>
using namespace std;
struct Tree {
int val;
Tree *left, *right;
// Constructor
Tree(int item){
val = item;
left = right = NULL;
}
};
map<int,int> mx_ind;
map<int,int> mn_ind;
//Function to fill the maps
void fill_maps(Tree* node,int level,int ind){
// Base case
if(node==NULL)return;
if(mx_ind.count(level))mx_ind[level] = max(ind,mx_ind[level]);
else mx_ind[level] = ind;
if(mn_ind.count(level))mn_ind[level] = min(ind,mn_ind[level]);
else mn_ind[level] = ind;
// Recursively call the function for the left and the right child
fill_maps(node->left, level+1, 2*ind+1);
fill_maps(node->right, level+1, 2*ind+2);
}
int MaxWidth(Tree* root){
int ans = 0;
fill_maps(root,0,0);
// Get the maximum width from width of all levels
for(auto lvl:mx_ind)ans = max(ans,mx_ind[lvl.first]-mn_ind[lvl.first]+1);
return ans;
}
int main(){
/*
Constructed Binary Tree
1
/ \
2 3
/ \
4 5
/ \
6 7
*/
struct Tree* root = new Tree(1);
root->left = new Tree(2);
root->right = new Tree(3);
root->left->left = new Tree(4);
root->right->right = new Tree(5);
root->left->left->left = new Tree(6);
root->right->right->right = new Tree(7);
int ans = MaxWidth(root);
cout<<ans<<'\n';
return 0;
}
输出
8
时间复杂度 - O(n)，其中 n 是树中的节点数。
空间复杂度 - O(n)，用于存储每一层的最左节点和最右节点。
方法 2
在这种方法中，我们将使用层序遍历，并使用其对应父节点的 ID 为所有节点分配 ID。对于每一层，我们可以通过从该层最后一个节点的宽度中减去第一个节点的 ID 来计算该层的宽度。然后，我们可以取所有宽度值的 最大值来获得所需的结果。
算法
步骤 1 - 创建树结构体 Tree。
步骤 1.1 - Tree 将包含一个整数 val 和两个指向自身的指针 left 和 right。
步骤 2 - 创建一个队列数据结构。
步骤 2.1 - 队列将包含一对，包含指向节点的指针及其对应的 ID。
步骤 3 - 对树进行层序遍历。
步骤 3.1 - 在每一层，将第一个和最后一个节点的 ID 存储在两个变量中。
步骤 3.2 - 在每一层的每个节点中，将节点的左子节点和右子节点以及 ID 2*i + 1 和 2*i + 2 推入队列。
步骤 3.3 - 该层的宽度的值计算为 last_node_ID - first_node_ID + 1。
步骤 3.4 - 取所有宽度值的 最大值以获得最大宽度。
步骤 4 - 返回答案。
示例
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
struct Tree {
int val;
Tree *left, *right;
// Constructor
Tree(int item){
val = item;
left = right = NULL;
}
};
int MaxWidth(Tree* root){
int ans = 0;
//Base Case
if(root==NULL)return ans;
queue<pair<Tree*,int>> que;
ans = 1;
que.push(make_pair(root,0));
//Level order traversal
while(!que.empty()){
int sz = que.size();
int first , last;
for(int i=0;i<sz;i++){
Tree *curr = que.front().first;
int id = que.front().second;
que.pop();
//First Node
if(i==0)first=id;
//Last Node
if(i==(sz-1))last=id;
if(curr->left!=NULL)que.push(make_pair(curr->left,2*id+1));
if(curr->right!=NULL)que.push(make_pair(curr->right,2*id+2));
}
// Taking the maximum of the width at each level
ans = max(ans,last-first+1);
}
return ans;
}
int main(){
/*
Constructed Binary Tree
1
/ \
2 3
/ \
4 5
/ \
6 7
*/
struct Tree* root = new Tree(1);
root->left = new Tree(2);
root->right = new Tree(3);
root->left->left = new Tree(4);
root->right->right = new Tree(5);
root->left->left->left = new Tree(6);
root->right->right->right = new Tree(7);
int ans = MaxWidth(root);
cout<<ans<<'\n';
return 0;
}
输出
8
时间复杂度 - O(n)，其中 n 是树中的节点数。
空间复杂度 - O(n)，用于存储每一层的最左节点和最右节点。
125 次浏览
