首页 > 试题广场 >

给定一棵树的根节点, 在已知该树最大深度的情况下, 求节点数

[问答题]

给定一棵树的根节点, 在已知该树最大深度的情况下, 求节点数最多的那一层并返回具体的层数。

如果最后答案有多层, 输出最浅的那一层，树的深度不会超过100000。实现代码如下，请指出代码中的多处错误：

 

struct Node {

    vector<Node*> sons;

};

 

void dfsFind(Node *node, int dep, int counter[]) {

    counter[dep]++;

 

    for(int i = 0; i < node.sons.size(); i++) {

        dfsFind(node.sons[i], dep, counter);

    }

}

 

int find(Node *root, int maxDep) {

    int depCounter[100000];

    dfsFind(root, 0, depCounter);

 

    int max, maxDep;

    for (int i = 1; i <= maxDep; i++) {

        if (depCounter[i] > max) {

            max = depCounter[i];

            maxDep = i;

        }

    }

    return maxDep;

}

添加回答
yxwithu头像 yxwithu
1. dfsFind函数中没有判断node为null的情况，应添加if(node == null) return ;
2. dfsFind函数中的递归, dep应为dep+1
3. find函数中max没有初始化，应改为max = 0;
4. find函数重新定义了maxDep，应删去
5. find函数中的for循环会引发函数越界，应改为for(int i = 0; i < maxDep; i++)
6. 删去maxDep = i;
7. find函数中应返回max
发表于 2018-01-26 11:10:30 回复(0)
国王的冕冠头像 国王的冕冠
1.dfsFind没有递归出口，应添加参数maxDep并加一句话 if (dep == maxDep) return; 
2.node是指针，调用sons应使用node->sons  
3.dfsFind里的递归语句参数不对，应为 dfsFind(node->sons[i], dep + 1, counter) 
4.find函数中的max和depCounter未清0 
5.find里的循环应为 for (int i = 0; i < maxDep; i++)
编辑于 2018-02-04 13:46:31 回复(2)
我是管小亮头像 我是管小亮 
/*
 *  Node 结构体，包含一个元素为 Node * 的向量
 *  用来存储树结构的父子关系
 */
struct Node {
    vector<Node*> sons;
};

/*
 *  深度优先遍历，用来遍历树并且对每层结点数计数
 *  node 为父节点的指针，dep 为深度，counter 为存储每层结点数的数组
 */
void dfsFind(Node *node, int dep, int counter[]) {
    counter[dep]++;                                 //  计数操作
    for(int i = 0; i < node->sons.size(); i++) {    //  错误 1 指针操作错误
        dfsFind(node->sons[i], dep + 1, counter);   //  错误 2 指针操作错误，深度控制不当
    }
}

/*
 *  find 函数，root 是树的根，maxDep 是树的最大深度
 */
int find(Node *root, int maxDep) {
    int depCounter[100003];               //  错误 3 存储树的每层结点数.可能存在越界问题
    dfsFind(root, 0, depCounter);         //  调用深度优先遍历函数，
                                          //  传入根和初始深度以及存储数每层结点数的数组
    int max = 1, res = 0;                 //  错误 4 未初始化、命名冲突
    for (int i = 1; i <= maxDep; i++) {    
        if (depCounter[i] > max) {
            max = depCounter[i];
            res = i;                      //  错误 5 被赋值变量错误
        }
    }
    return res;                           //  错误 6 返回错误变量
}
修改版本的代码如上↑
编辑于 2020-08-06 23:06:56 回复(1)
纵横捭阖头像 纵横捭阖
1.dfsFind()函数中首先添加这样的代码 if(node==null){ return 0; }
2.find()函数添加 if(root==null){ return 0; }
3.指针错误： for(int i = 0; i < node.sons.size(); i++) 一行改成 for(int i = 0; i < node->sons.size(); i++) 
4.find函数中，  int max, maxDep;一行改成：int max=0;后面的去掉。
5.dfsFind中添加上侧添加dep++;
发表于 2018-01-30 14:35:23 回复(0)
snoopy-NO2头像 snoopy-NO2
int depCounter[100000];
dfsFind(root, 0, depCounter);        //这个部分直接这样调用函数
int max, maxDep;
for (int i = 1; i <= maxDep; i++) {
if (depCounter[i] > max) {
max = depCounter[i];           //这个地方直接用depCounter的值，函数dfsFind中形参counter的值能传过来给depCounter吗？
maxDep = i;
}
dfsFind需不需要返回值呢？
是不是int depCounter[100000]; 要在全局定义
编辑于 2019-08-09 11:14:16 回复(0)
流心汤圆头像 流心汤圆
python飘过
发表于 2022-07-19 15:53:36 回复(0)
牛客801912799号头像 牛客801912799号
1. dfsFind(root,0,depCounter)函数，参量dep一直没有变化，不论是哪一层的节点，都加给了第0层。
2. max没有初始化，里面可能是随便一个值，这个值可能很大，以至于最后的结果是错的。
发表于 2022-03-26 11:16:31 回复(0)
牛客853724388号头像 牛客853724388号
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 5e5 + 10;  //  设置数组最大长度
const int MAX_NUM = 100;    //  设置元素最大值

int n;
int a[MAXN];                //  题目给定数组序列
int l[MAXN];                //  l[i] 表示第 i 个元素作为最小值最大区间的左界
int r[MAXN];                //  r[i] 表示第 i 个元素作为最小值最大区间的右界
int s[MAXN];                //  s[i] 表示前 i 个元素的和

//  初始化函数，预处理前缀和
void init()
{
    s[1] = a[1];
    for (int i = 2; i <= n; i++)
    {
        s[i] = s[i - 1] + a[i];
    }
}

int main()
{
    scanf("%d", &n);

    for (int i = 1; i <= n; ++i)
    {
        scanf("%d", a + i);
    }

    init();

    //  从左往右遍历，获取 l
    int L, R;
    for (int i = 1; i <= MAX_NUM; ++i)
    {
        L = 1;
        for (int j = 1; j <= n; ++j)
        {
            if (a[j] < i)
            {
                L = j + 1;
            }
            if (a[j] == i)
            {
                l[j] = L;
            }
        }
    }

    //  从右往左遍历，获取 r
    for (int i = 1; i <= MAX_NUM; ++i)
    {
        R = n;
        for (int j = n; j >= 1; --j)
        {
            if (a[j] < i)
            {
                R = j - 1;
            }
            if (a[j] == i)
            {
                r[j] = R;
            }
        }
    }

    //  枚举取最优解
    int ans = 0;
    for (int i = 1; i <= n; ++i)
    {
        ans = max(ans, (s[r[i]] - s[l[i] - 1]) * a[i]);
    }

    cout << ans << endl;

    return 0;
}
发表于 2020-10-23 15:20:11 回复(0)
玦小景头像 玦小景
递归调用时， 进入下一层应该递增dep ：
    dfsFind(node.sons[i], dep + 1, counter);
int find（Node *root, int maxDep） 传入的 ；maxDep参数没有作用 ，被函数内的局部变量覆盖，可以删除；
数组depCounter 需要初始化为全零；
整型 max，maxDep需要初始化；
for循环的条件 i < maxDep 错误， 改为i < 99999 ;
或者 修改 dfsFind 函数，传入一个整形引用，用以基础达到过的最大深度，然后以该深度为循环上限。
发表于 2020-07-17 17:26:23 回复(0)
StarEvil头像 StarEvil
struct Node {
    vector<Node*> sons;
};

void dfsFind(Node *node, int dep, int counter[]) {
    counter[dep]++;                            
    for(int i = 0; i < node->sons.size(); i++) {     //  错误 1 指针操作错误
        dfsFind(node->sons[i], dep + 1, counter);   //  错误 2 指针操作错误，深度控制不当
    }
}

int find(Node *root, int maxDep) {
    int depCounter[100000];             
    dfsFind(root, 0, depCounter);         
                                     
    int max = 1, maxIndex = 0;                 //  错误 3 未初始化、命名冲突
    for (int i = 1; i <= maxDep; i++) {    
        if (depCounter[i] > max) {
            max = depCounter[i];
            maxIndex = i;                         //  错误 4 被赋值变量错误
        }
    }
    return maxIndex;                           //  错误 5 返回错误变量
}

发表于 2020-07-08 17:38:41 回复(0)
傻歌‘头像 傻歌‘
dfsFind(node.sons[i], dep, counter); 改为 dfsFind(node.sons[i], dep+1, counter);
int max=depCounter[0], maxDep=0;

发表于 2019-12-11 22:03:00 回复(0)
白色的蜻蜓头像 白色的蜻蜓 

	struct Node {





	    vector<Node*> sons;





	};





	 





	void dfsFind(Node *node, int dep, int counter[]) {





	    counter[dep]+=node.sons.size();





	    for(int i = 0; i < node.sons.size(); i++) {





	        dfsFind(node.sons[i], dep++, counter);





	    }





	}





	 





	int find(Node *root, int maxDep) {





	    int depCounter[100000];





	memset(depCounter,0,sizeof(depCounter);





	    dfsFind(root, 1, depCounter);





	 





	    int max, maxDep;





	   max=0;





	    for (int i = 1; i <= maxDep; i++) {





	        if (depCounter[i] > max) {





	            max = depCounter[i];





	            maxDep = i;





	        }





	    }





	    return maxDep;





	}

发表于 2019-07-12 17:41:54 回复(0)
Cyx201810170421729头像 Cyx201810170421729 

	void dfsFind(Node *node, int dep, int counter[]) {





	    counter[dep]++;





	 





	    for(int i = 0; i < node.sons.size(); i++) {





	        dfsFind(node.sons[i], dep, counter);//此处应该为dep+1





	    }





	}





	





	




	int find(Node *root, int maxDep) {





	    int depCounter[100000];





	    dfsFind(root, 0, depCounter);





	 





	    int max,maxDep; //max未初始化,重复定义了maxDep,可定义为maxDepIdex





	    for (int i = 1; i <= 100000; i++) { //此处应该修改为(int i = maxDep - 1; i >=0; i--) 因为必须是输出最浅的一层,理应采用倒序遍历





	        if (depCounter[i] > max) {//此处应该修改为depCounter[i] >= max 因为可能最后答案有多层,所以设为>=就不会忽略结果相同的层





	            max = depCounter[i];





	            maxDep = i;//此处应该修改为 maxDepIdex= i;





	        }





	    }





	    return maxDep;





	}

发表于 2019-03-15 11:14:32 回复(1)
ryanx35头像 ryanx35
  1. dfsFind(node.sons[i], dep, counter); 语句中，递归调用下一层时第二个参数应为dep+1
  2. for (int i = 1; i <= maxDep; i++) { 语句中，由于程序其他函数的写法是按照根节点为第0层，因此需要从下标0开始统计，即改为i=0;i<maxDep
  3. 整型变量max没有赋初值，应当在定义之后赋初值0
  4.   maxDep = i;  这一句去除，maxDep在运行过程中应当是不变的
  5. 为了返回具体层数，max = depCounter[i];一句应当改为max=i; 同时由于程序中根节点为第0层，而通常认为根节点为第1层，所以返回值改为max+1
发表于 2019-03-14 11:42:46 回复(0)
枫xh头像 枫xh
1.dfsFind函数应该返回int数组counter，或者使用引用调用。
2.应该为整型变量max, maxDep提供初值，可初始化为 int max=depCounter[0], maxDep=1;
发表于 2019-03-04 20:54:32 回复(0)
一吻以谢天下头像 一吻以谢天下
1.

 for(int i = 0; i < node.sons.size(); i++) { 

        dfsFind(node.sons[i], dep + 1, counter); 

    }

2

int max = 0, maxPos; 

    for (int i = 1; i <= maxDep; i++) { 

        if (depCounter[i] > max) { 

            max = depCounter[i]; 

            maxPos = i; 

        } 

    }

return max;

发表于 2018-07-29 01:46:18 回复(1)
牛客5709732号头像 牛客5709732号
我想说这题目要求2个啊，一个是最浅层数，还有最多的层节点树
发表于 2018-03-24 18:08:10 回复(0)
已注销头像 已注销
个人认为其实不考虑为空的情况也是可以的，因为建树过程中，每次为父节点添加儿子时都应该创建一下子结点的，另外，有明显的指针操作错误。
发表于 2018-01-26 16:39:10 回复(0)
提交观点

问题信息

测试开发工程师 测试工程师 2018 字节跳动
上传者：小小
难度：
18条回答 6557浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号