C++ 华为OJ 求解二叉树的宽度（行列实现）

C++ 华为OJ 求解二叉树的宽度（队列实现）

我们可以把二叉树中每层的节点依次放入一个队列中。设置一个变量width用于存储树的宽度。每一层的节点入队时计算该层节点的数目，如果该层次节点的数目大于width的值，那么把该层次节点的数目赋给width.如此，对二叉树按层遍历一遍之后width中保存的就是该二叉树的宽度。

【源码实现】

int WidthOfTheTree(Node* pRoot)  

{  

    if(pRoot==NULL)  

        return 0;  

    queue<Node*> MyQueue2;  

    MyQueue2.push(pRoot);  

    int width=1;  

    int curwidth=1;  

    int nextwidth=0;  

    while(!MyQueue2.empty())  

    {  

        while(curwidth!=0)  

        {  

            Node* pTmp=MyQueue2.front();  

            MyQueue2.pop();  

            curwidth--;  

            if(pTmp->pLeft!=NULL)  

            {  

                MyQueue2.push(pTmp->pLeft);  

                nextwidth++;  

            }  

            if (pTmp->pRight!=NULL)  

            {  

                MyQueue2.push(pTmp->pRight);  

                nextwidth++;  

            }  

        }  

        if(nextwidth>width)  

            width=nextwidth;  

        curwidth=nextwidth;  

        nextwidth=0;  

    }  

    return width;  

}