本文共 2123 字，大约阅读时间需要 7 分钟。

二叉树的宽度是指具有节点数目最多的那一层的节点个数。我们需要通过给定的父节点关系，构建二叉树并计算其宽度。

输入格式

输入共有n行：

• 第一行是一个整数n，表示有n个结点，编号为1至n，结点1为树根。
• 接下来的n-1行，每行有两个整数x和y，表示在二叉树中x为y的父节点。第一次出现的x，其y为左孩子；若x已经有左孩子，则y为右孩子。

输出格式

输出二叉树的宽度。

思路

代码

#include 
   
    
#include 
    
     
using namespace std;
int bfs(vector
     
       &children, int n) {
    vector
      
        nodeQueue;
    nodeQueue.push_back(1); // 根节点1
    int maxLevelWidth = 0;
    int currentLevelSize = 1;
    while (!nodeQueue.empty()) {
        int nextLevelSize = 0;
        for (int i = 0; i < currentLevelSize; ++i) {
            int current = nodeQueue[i];
            if (children[current] == 0) {
                // 左孩子未存在，存为左孩子
                children[current] = ++lastNodeID;
                nextLevelSize++;
            } else if (children[current] != 0) {
                // 已经有左孩子，存为右孩子
                children[current] = ++lastNodeID;
                nextLevelSize++;
            }
            // 检查是否是最后一个节点，避免超出数组大小
            if (children[current] > n) {
                children[current] = 0;
            }
        }
        if (nextLevelSize > maxLevelWidth) {
            maxLevelWidth = nextLevelSize;
        }
        nodeQueue.clear();
        nodeQueue.insert(nodeQueue.end(), nextLevelSize, children);
        currentLevelSize = nextLevelSize;
    }
    return maxLevelWidth;
}
int main() {
    vector
       
         children(n + 1, 0); // children[0]不使用
    int lastNodeID = 1;
    int n;
    cin >> n;
    for (int i = 1; i < n; ++i) {
        int x, y;
        cin >> x >> y;
        if (children[x] == 0) {
            children[x] = y;
            lastNodeID = y;
        } else {
            children[x] = y;
            lastNodeID = y;
        }
    }
    int width = bfs(children, n);
    cout << width << endl;
    return 0;
}
       
      
     
    
   

代码解释

转载地址：http://csrfk.baihongyu.com/