[经典面试题]二叉树宽度

（1）二叉树最大宽度

/*———————————————* 日期：2015-03-07* 作者：SJF0115* 题目: 二叉树的最大宽度* 来源：经典面试题* 博客：———————————————–*/;struct TreeNode{int val;TreeNode *left;TreeNode *right;TreeNode(int x):val(x),left(NULL),right(NULL){}};// 二叉树的最大宽度int MaxWidthBinaryTree(TreeNode *root){if(root == NULL){return 0;}<TreeNode*> curLevel;// 下一层queue<TreeNode*> nextLevel;// 最大宽度int max = 0;// 当前层宽度int width = 0;// 加入队列curLevel.push(root);TreeNode *node;while(!curLevel.empty()){width = 0;while(!curLevel.empty()){++width;if(width > max){max = width;}//ifnode = curLevel.front();curLevel.pop();// 左子树if(node->left != NULL){nextLevel.push(node->left);}(node->right != NULL){nextLevel.push(node->right);}//if}//whileswap(curLevel,nextLevel);}//whilereturn max;}//按先序序列创建二叉树int CreateBTree(TreeNode*& T){int data;//按先序次序输入二叉树中结点的值,-1表示空树cin>>data;if(data == -1){T = NULL;}else{T = new TreeNode(data);//构造左子树CreateBTree(T->left);//构造右子树CreateBTree(T->right);}return 0;}int main() {TreeNode *root = NULL;CreateBTree(root);int result = MaxWidthBinaryTree(root);cout<<result<<endl;return 0;}

（2）二叉树各层宽度

/*———————————————* 日期：2015-03-07* 作者：SJF0115* 题目: 二叉树的最大宽度* 来源：经典面试题* 博客：———————————————–*/;struct TreeNode{int val;TreeNode *left;TreeNode *right;TreeNode(int x):val(x),left(NULL),right(NULL){}};// 二叉树宽度vector<int> WidthBinaryTree(TreeNode *root){vector<int> level;if(root == NULL){return level;}<TreeNode*> curLevel;// 下一层queue<TreeNode*> nextLevel;// 当前层宽度int width = 0;// 加入队列curLevel.push(root);TreeNode *node;while(!curLevel.empty()){width = 0;while(!curLevel.empty()){++width;node = curLevel.front();curLevel.pop();// 左子树if(node->left != NULL){nextLevel.push(node->left);}(node->right != NULL){nextLevel.push(node->right);}//if}//whilelevel.push_back(width);swap(curLevel,nextLevel);}//whilereturn level;}//按先序序列创建二叉树int CreateBTree(TreeNode*& T){int data;//按先序次序输入二叉树中结点的值,-1表示空树cin>>data;if(data == -1){T = NULL;}else{T = new TreeNode(data);//构造左子树CreateBTree(T->left);//构造右子树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]<<“个节点”<<endl;};}

，乐观者在灾祸中看到机会;悲观者在机会中看到灾祸