（1）二叉樹(shù)最大寬度

/*---------------------------------------------* 日期：2015-03-07* 作者：SJF0115* 題目: 二叉樹(shù)的最大寬度* 來(lái)源：經(jīng)典面試題* 博客：-----------------------------------------------*/#include <iostream>#include <queue>using namespace std;struct TreeNode{int val;TreeNode *left;TreeNode *right;TreeNode(int x):val(x),left(NULL),right(NULL){}};// 二叉樹(shù)的最大寬度int MaxWidthBinaryTree(TreeNode *root){if(root == NULL){return 0;}//if// 當(dāng)前層queue<TreeNode*> curLevel;// 下一層queue<TreeNode*> nextLevel;// 最大寬度int max = 0;// 當(dāng)前層寬度int width = 0;// 加入隊(duì)列curLevel.push(root);TreeNode *node;while(!curLevel.empty()){width = 0;while(!curLevel.empty()){++width;if(width > max){max = width;}//ifnode = curLevel.front();curLevel.pop();// 左子樹(shù)if(node->left != NULL){nextLevel.push(node->left);}//if// 右子樹(shù)if(node->right != NULL){nextLevel.push(node->right);}//if}//whileswap(curLevel,nextLevel);}//whilereturn max;}//按先序序列創(chuàng)建二叉樹(shù)int CreateBTree(TreeNode*& T){int data;//按先序次序輸入二叉樹(shù)中結(jié)點(diǎn)的值,-1表示空樹(shù)cin>>data;if(data == -1){T = NULL;}else{T = new TreeNode(data);//構(gòu)造左子樹(shù)CreateBTree(T->left);//構(gòu)造右子樹(shù)CreateBTree(T->right);}return 0;}int main() {TreeNode *root = NULL;CreateBTree(root);int result = MaxWidthBinaryTree(root);cout<<result<<endl;return 0;}

（2）二叉樹(shù)各層寬度

/*---------------------------------------------* 日期：2015-03-07* 作者：SJF0115* 題目: 二叉樹(shù)的最大寬度* 來(lái)源：經(jīng)典面試題* 博客：-----------------------------------------------*/#include <iostream>#include <queue>#include <vector>using namespace std;struct TreeNode{int val;TreeNode *left;TreeNode *right;TreeNode(int x):val(x),left(NULL),right(NULL){}};// 二叉樹(shù)寬度vector<int> WidthBinaryTree(TreeNode *root){vector<int> level;if(root == NULL){return level;}//if// 當(dāng)前層queue<TreeNode*> curLevel;// 下一層queue<TreeNode*> nextLevel;// 當(dāng)前層寬度int width = 0;// 加入隊(duì)列curLevel.push(root);TreeNode *node;while(!curLevel.empty()){width = 0;while(!curLevel.empty()){++width;node = curLevel.front();curLevel.pop();// 左子樹(shù)if(node->left != NULL){nextLevel.push(node->left);}//if// 右子樹(shù)if(node->right != NULL){nextLevel.push(node->right);}//if}//whilelevel.push_back(width);swap(curLevel,nextLevel);}//whilereturn level;}//按先序序列創(chuàng)建二叉樹(shù)int CreateBTree(TreeNode*& T){int data;//按先序次序輸入二叉樹(shù)中結(jié)點(diǎn)的值,-1表示空樹(shù)cin>>data;if(data == -1){T = NULL;}else{T = new TreeNode(data);//構(gòu)造左子樹(shù)CreateBTree(T->left);//構(gòu)造右子樹(shù)CreateBTree(T->right);}return 0;}int main() {TreeNode *root = NULL;CreateBTree(root);vector<int> result = WidthBinaryTree(root);for(int i = 0;i < result.size();++i){cout<<"第"<<i+1<<"層->"<<result[i]<<"個(gè)節(jié)點(diǎn)"<<endl;}//forreturn 0;}

總結(jié)

以上是生活随笔為你收集整理的[经典面试题]二叉树宽度的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。