二叉树的宽度

恋喵大鲤鱼

发布于 2024-05-24 14:29:48

510

发布于 2024-05-24 14:29:48

文章被收录于专栏：C/C++基础

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

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

比如上图中，第 1 层有 1 个结点，第 2 层有 2 个结点，第 3 层有 4 个结点，第 4 层有 1 个结点。可知，第 3 层的结点数最多，所以这棵二叉树的宽度是 4。

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

具体实现：

//求二叉树的宽度  
int treeWidth(BinaryTreeNode *pRoot) {
    if (pRoot == NULL) return 0;
    
    queue<BinaryTreeNode*> myQueue;  
    myQueue.push(pRoot);		// 将根结点入队列
	int nWidth = 1;				// 二叉树的宽度
    int nCurLevelWidth = 1;		// 记录当前层的宽度
    BinaryTreeNode *pCur = NULL;
  
	// 队列不为空
    while (!myQueue.empty()) {
        while (nCurLevelWidth != 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);
            nCurLevelWidth--;
        }
  
        nCurLevelWidth = myQueue.size();
        nWidth = nCurLevelWidth > nWidth ? nCurLevelWidth : nWidth;
    }
    return nWidth;  
}