求二叉树的深度和宽度
1 二叉树的深度
题目： 输入一个二叉树的根节点，求该树的深度。从根节点到叶子节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度包含的节点数为为树的深度，即二叉树节点的层数。
二叉树的节点定义： 假定二叉树的节点定义如下：
struct BinaryTreeNode{
int m_value;
BinaryTreeNode* m_pLeft;
BinaryTreeNode* m_pRight;
};二叉树示例： 以图深度为四的二叉树为例，其先先根遍历序列为：{1,2,4,5,7,3,6}，中根遍历序列为：{4,2,7,5,1,3,6}，根据先根序列和中根序列即可构造唯一的二叉树，构造的具体实现可参见：二叉树的构造与遍历。很显然，该二叉树有4层节点，所以其高度是４。
求解思路： 根据题目的定义，我们可以用先根次序来遍历二叉树中所有根节点到叶节点的路径，来得到最长的路径就是二叉树的高度。但是这样的代码量较为冗长，我们可以采用递归的方式解决。
我们可以从根节点即左右子树来理解二叉树的深度。对于任意一棵非空二叉树，有如下四种情况：
（1）如果一颗树只有一个节点，它的深度是1；
（2）如果根节点只有左子树而没有右子树，那么二叉树的深度应该是其左子树的深度加1；
（3）如果根节点只有右子树而没有左子树，那么二叉树的深度应该是其右树的深度加1；
（4）如果根节点既有左子树又有右子树，那么二叉树的深度应该是其左右子树的深度较大值加1；
实现代码：
int treeDepth(BinaryTreeNode* root){
if(root==NULL){
return 0;
}
int nLeft=treeDepth(root->m_pLeft);
int nRight=treeDepth(root->m_pRight);
return nLeft>nRight?nLeft+1:nRight+1;
}2 二叉树的宽度
题目： 给定一颗二叉树，求二叉树的宽度。
宽度的定义： 二叉树的宽度定义为具有最多结点数的层中包含的结点数。
比如上图中，第1层有1个节点， 第2层有2个节点， 第3层有4个节点， 第4层有1个节点，可知，第3层的结点数最多，所以这棵二叉树的宽度就是4。
求解思路： 这里需要用到二叉树的层次遍历，即广度优先周游。在层次遍历的过程中，通过读取队列中保留的上一层的节点数来记录每层的节点数，以获取所有层中最大的节点数。关于二叉树的广度优先周游，参考：二叉树的构造与遍历。
具体实现：
//求二叉树的宽度
int treeWidth(BinaryTreeNode *pRoot){
if (pRoot == NULL)
return 0;
int nLastLevelWidth = 0;//记录上一层的宽度
int nCurLevelWidth = 0;//记录当前层的宽度
queue<BinaryTreeNode*> myQueue;
myQueue.push(pRoot);//将根节点入队列
int nWidth = 1;//二叉树的宽度
nLastLevelWidth = 1;
BinaryTreeNode *pCur = NULL;
while (!myQueue.empty())//队列不空
{
while (nLastLevelWidth!= 0){
pCur = myQueue.front();//取出队列头元素
myQueue.pop();//将队列头元素出对
if (pCur->m_pLeft != NULL)
myQueue.push(pCur->m_pLeft);
if (pCur->m_pRight != NULL)
myQueue.push(pCur->m_pRight);
nLastLevelWidth--;
}
nCurLevelWidth = myQueue.size();
nWidth = nCurLevelWidth > nWidth ? nCurLevelWidth : nWidth;
nLastLevelWidth = nCurLevelWidth;
}
return nWidth;
} 参考文献
[1]剑指Offer.何海涛.电子工业出版社. [2]求二叉树的深度和宽度
腾讯云开发者
