資料結構
網路
關係資料庫管理系統 (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 次瀏覽
