[已解决]求二叉树深度，为什么只有80分

zhangjinxuan

描述和格式见后面的图片

输入样例：

1. 7
   
2. 2 7
   
3. 3 6
   
4. 4 5
   
5. 0 0
   
6. 0 0
   
7. 0 0
   
8. 0 0

复制代码

输出样例：

1. 4

复制代码

我的代码：

1. #include <cstdio>
   
2. #include <algorithm>
   
3. using namespace std;
   
4. 
   
5. int n, a[1000001], d[1000001], x, y, ans = -(1 << 30);
   
6. 
   
7. int main() {
   
8.         scanf("%d", &n);
   
9.         d[1] = 1;
   
10.         for (int i = 1; i <= n; ++i) {
    
11.                 scanf("%d%d", &x, &y);
    
12.                 if (x) ans = max(d[x] = d[i] + 1, ans);
    
13.                 if (y) ans = max(d[y] = d[i] + 1, ans);
    
14.         }
    
15.         printf("%d", ans);
    
16. }

复制代码

最佳答案

月排行榜 / 总排行榜

人造人

2022-10-27 23:52:51

稍微改一改

1. #include <iostream>
   
2. #include <vector>
   
3. #include <array>
   
4. #include <algorithm>
   
5. 
   
6. using std::vector, std::array;
   
7. using std::cin, std::cout, std::endl;
   
8. using std::istream;
   
9. using std::max;
   
10. 
    
11. using tree_t = vector<array<size_t, 2>>;
    
12. 
    
13. istream &operator>>(istream &is, tree_t &tree) {
    
14.     tree_t temp; temp.push_back({});    // 不使用tree[0]
    
15.     size_t count; is >> count;
    
16.     for(size_t i = 0; i < count; ++i) {
    
17.         array<size_t, 2> a; is >> a[0] >> a[1];
    
18.         temp.push_back(a);
    
19.     }
    
20.     return tree = temp, is;
    
21. }
    
22. 
    
23. size_t get_depth(const tree_t &tree, size_t node, size_t init) {
    
24.     if(!node) return init;
    
25.     return ++init, max(get_depth(tree, tree[node][0], init), get_depth(tree, tree[node][1], init));
    
26. }
    
27. 
    
28. int main() {
    
29.     tree_t tree; cin >> tree;
    
30.     cout << get_depth(tree, 1, 0) << endl;
    
31.     return 0;
    
32. }
    

复制代码

跳转到最佳答案楼层

傻眼貓咪

题目要求建立一个二叉树，至少要有二叉树构造吧？class 或 struct

人造人

这个分数是怎么算的？

人造人

不知道对不对，多给几组输入/输出看看

1. #include <iostream>
   
2. #include <vector>
   
3. #include <array>
   
4. #include <algorithm>
   
5. 
   
6. using std::vector, std::array;
   
7. using std::cin, std::cout, std::endl;
   
8. using std::istream;
   
9. using std::max;
   
10. 
    
11. using tree_t = vector<array<size_t, 2>>;
    
12. 
    
13. istream &operator>>(istream &is, tree_t &tree) {
    
14.     tree_t temp; temp.push_back({});    // 不使用tree[0]
    
15.     size_t count; is >> count;
    
16.     for(size_t i = 0; i < count; ++i) {
    
17.         array<size_t, 2> a;
    
18.         is >> a[0] >> a[1];
    
19.         temp.push_back(a);
    
20.     }
    
21.     return tree = temp, is;
    
22. }
    
23. 
    
24. size_t get_depth(const tree_t &tree, size_t node, size_t init) {
    
25.     if(!node) return init;
    
26.     return max(get_depth(tree, tree[node][0], init + 1), get_depth(tree, tree[node][1], init + 1));
    
27. }
    
28. 
    
29. int main() {
    
30.     tree_t tree; cin >> tree;
    
31.     cout << get_depth(tree, 1, 0) << endl;
    
32.     return 0;
    
33. }
    

复制代码

人造人

傻眼貓咪 发表于 2022-10-27 22:50
题目要求建立一个二叉树，至少要有二叉树构造吧？class 或 struct

题目没有说把二叉树建立成什么形式
我想直接在数组中保存结点的形式也是可以的

人造人

稍微改一改

1. #include <iostream>
   
2. #include <vector>
   
3. #include <array>
   
4. #include <algorithm>
   
5. 
   
6. using std::vector, std::array;
   
7. using std::cin, std::cout, std::endl;
   
8. using std::istream;
   
9. using std::max;
   
10. 
    
11. using tree_t = vector<array<size_t, 2>>;
    
12. 
    
13. istream &operator>>(istream &is, tree_t &tree) {
    
14.     tree_t temp; temp.push_back({});    // 不使用tree[0]
    
15.     size_t count; is >> count;
    
16.     for(size_t i = 0; i < count; ++i) {
    
17.         array<size_t, 2> a; is >> a[0] >> a[1];
    
18.         temp.push_back(a);
    
19.     }
    
20.     return tree = temp, is;
    
21. }
    
22. 
    
23. size_t get_depth(const tree_t &tree, size_t node, size_t init) {
    
24.     if(!node) return init;
    
25.     return ++init, max(get_depth(tree, tree[node][0], init), get_depth(tree, tree[node][1], init));
    
26. }
    
27. 
    
28. int main() {
    
29.     tree_t tree; cin >> tree;
    
30.     cout << get_depth(tree, 1, 0) << endl;
    
31.     return 0;
    
32. }
    

复制代码

zhangjinxuan

人造人 发表于 2022-10-27 23:52
稍微改一改

我只是想说，我的这个代码有没有问题

zhangjinxuan

傻眼貓咪 发表于 2022-10-27 22:50
题目要求建立一个二叉树，至少要有二叉树构造吧？class 或 struct

我的代码有问题吗？

人造人

zhangjinxuan 发表于 2022-10-28 07:35
我只是想说，我的这个代码有没有问题

https://fishc.com.cn/forum.php?m ... 003&pid=6029054
不知道对不对，"""多给几组输入/输出看看"""

https://fishc.com.cn/forum.php?m ... 003&pid=6029011
""" 这个分数是怎么算的？"""

分数怎么算的？也许就是因为你的代码写的不够优雅，扣了你20分

多给几组输入/输出看看
就一组输入/输出看不出问题

还有，在哪组输入/输出上面出了问题？
你的刷题网站不显示出问题的输入/输出？


我的回复都是有用的，你的看我的回复
我问你的问题就是你提问题的时候漏掉的那部分
没有你漏掉的那部分，问题就很不好解决

人造人

zhangjinxuan 发表于 2022-10-28 07:35
我的代码有问题吗？

有肯定是有，首先的第一个问题就是你的代码写的不够优雅
要我做裁判，凭这一点就扣你20分不行吗？
^_^

确实在我看来，问题不是对就是错，不是0分就是100分
如果你非要细分的话，那就是在答案正确的前提下，看你代码写的怎么样

所以我要问你计分规则是怎么样的，因为在我看来就是上面说到的那样
代码写的不够优雅，扣20分
^_^

人造人

zhangjinxuan 发表于 2022-10-28 07:35
我只是想说，我的这个代码有没有问题

可是我想知道我的代码有没有问题

人造人

知道吗？一个不能重现的问题基本无解
如果知道了出问题的那组输入/输出
可以非常容易的找出代码中的问题
用调试器把程序运行起来，输入出问题的那个输入数据，一行代码一行代码的执行，看执行结果，如果执行结果即将脱离正确答案的那条路径
那问题就在这里了，如果是函数调用，那就重新运行程序，一样的输入，在这个函数的时候跟进去，一样的方法，看看哪行代码脱离了正确答案

人造人

调试程序是作为程序员的必备技能，同意吗？同意吧？

dolly_yos2

考虑这组输入，应该不是能产生问题的最小输入，但是也比较小好分析了

1. 7
   
2. 5 7
   
3. 4 6
   
4. 0 0
   
5. 0 0
   
6. 2 0
   
7. 0 0
   
8. 0 3

复制代码

人造人

dolly_yos2 发表于 2022-10-28 10:38
考虑这组输入，应该不是能产生问题的最小输入，但是也比较小好分析了

这是3棵树吧？

人造人

dolly_yos2 发表于 2022-10-28 10:38
考虑这组输入，应该不是能产生问题的最小输入，但是也比较小好分析了

好吧，是我不认真看错了
抱歉，^_^

人造人

1. 7
   
2. 5 7
   
3. 4 6
   
4. 0 0
   
5. 0 0
   
6. 2 0
   
7. 0 0
   
8. 0 3

复制代码

就是 dolly_yos2 给出的这个输入/输出
你的这个程序在这个输入上，输出的结果是错误的
正确答案是4，你的程序给出了3
调试了一下你的程序，看不懂你在做什么
你这个数组d中存储的是什么？
你求树的深度用的什么方法？
对于这个输入，1的左孩子是5，右孩子是7
你这个数组d里面没有5和7
你这个数组里面存储的这些值表示什么意思？

人造人

上面的那个程序从逻辑上来讲是不对的，而且也不需要init参数
再改一改

1. #include <iostream>
   
2. #include <vector>
   
3. #include <array>
   
4. #include <algorithm>
   
5. 
   
6. using std::vector, std::array;
   
7. using std::cin, std::cout, std::endl;
   
8. using std::istream;
   
9. using std::max;
   
10. 
    
11. using tree_t = vector<array<size_t, 2>>;
    
12. 
    
13. istream &operator>>(istream &is, tree_t &tree) {
    
14.     tree_t temp; temp.push_back({});    // 不使用tree[0]
    
15.     size_t count; is >> count;
    
16.     for(size_t i = 0; i < count; ++i) {
    
17.         array<size_t, 2> a; is >> a[0] >> a[1];
    
18.         temp.push_back(a);
    
19.     }
    
20.     return tree = temp, is;
    
21. }
    
22. 
    
23. size_t get_depth(const tree_t &tree, size_t node) {
    
24.     if(!node) return 0;
    
25.     return max(get_depth(tree, tree[node][0]), get_depth(tree, tree[node][1])) + 1;
    
26. }
    
27. 
    
28. int main() {
    
29.     tree_t tree; cin >> tree;
    
30.     cout << get_depth(tree, 1) << endl;
    
31.     return 0;
    
32. }
    

复制代码

柿子饼同学

zhangjinxuan 发表于 2022-10-28 07:35
我的代码有问题吗？

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. struct node{
   
5.         int lc, rc;
   
6. } tree[1000005];
   
7. int n, l, r, ans;
   
8. 
   
9. void dfs(int pos, int dep){
   
10.         if(!tree[pos].lc && !tree[pos].rc){
    
11.                 ans = max(ans, dep);
    
12.         }
    
13.         if(tree[pos].lc) dfs(tree[pos].lc, dep + 1);
    
14.         if(tree[pos].rc) dfs(tree[pos].rc, dep + 1);
    
15. }
    
16. 
    
17. int main(){
    
18.         ios::sync_with_stdio(0);
    
19.         cin.tie(0);
    
20.        
    
21.         cin >> n;
    
22.         for(int i = 1; i <= n; i++){
    
23.                 cin >> l >> r;
    
24.                 tree[i] = {l, r};
    
25.         }
    
26. 
    
27.         dfs(1, 1);
    
28. 
    
29.         cout << ans ;
    
30.        
    
31.         return 0;
    
32. }
    

复制代码

傻眼貓咪

zhangjinxuan 发表于 2022-10-28 07:35
我的代码有问题吗？

应该是没有问题，因为可以得到 80 分，我猜可能不完善吧，或是像人造人大佬说的那样，不够优雅吧