求二叉树的深度和宽度

二叉树的深度

题目：

输入一个二叉树的根节点，求该树的深度。从根节点到叶子节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度包含的节点数为为树的深度，即二叉树节点的层数。

二叉树的节点定义

假定二叉树的节点定义如下：

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;
}

二叉树的宽度

题目

给定一颗二叉树，求二叉树的宽度。

宽度的定义

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

比如上图中，第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;  
}