Question

二叉树的深度怎么算？

Answer 1

1. 一颗树只有一个节点，它的深度是1；

2. 根节点只有左子树而没有右子树，那么二叉树的深度应该是其左子树的深度加1；

3. 根节点只有右子树而没有左子树，那么二叉树的深度应该是其右树的深度加1；

4. 根节点既有左子树又有右子树，那么二叉树的深度应该是其左右子树的深度较大值加1

二叉树的宽度算法如下：

• 宽度的定义： 

二叉树的宽度定义为具有最多结点数的层中包含的结点数。

• 求解思路： 

这里需要用到二叉树的层次遍历，即广度优先周游。在层次遍历的过程中，通过读取队列中保留的上一层的节点数来记录每层的节点数，以获取所有层中最大的节点数。

• 具体实现：
  

//求二叉树的宽度  

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;  

}

参考资料

二叉树的构造与遍历.csdn博客[引用时间2018-5-2]