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

zhangjinxuan

描述和格式见后面的图片

输入样例：

7
2 7
3 6
4 5
0 0
0 0
0 0
0 0

输出样例：

4

我的代码：

#include <cstdio>
#include <algorithm>
using namespace std;

int n, a[1000001], d[1000001], x, y, ans = -(1 << 30);

int main() {
        scanf("%d", &n);
        d[1] = 1;
        for (int i = 1; i <= n; ++i) {
                scanf("%d%d", &x, &y);
                if (x) ans = max(d[x] = d[i] + 1, ans);
                if (y) ans = max(d[y] = d[i] + 1, ans);
        }
        printf("%d", ans);
}

最佳答案

月排行榜 / 总排行榜

人造人

2022-10-27 23:52:51

稍微改一改

#include <iostream>
#include <vector>
#include <array>
#include <algorithm>

using std::vector, std::array;
using std::cin, std::cout, std::endl;
using std::istream;
using std::max;

using tree_t = vector<array<size_t, 2>>;

istream &operator>>(istream &is, tree_t &tree) {
    tree_t temp; temp.push_back({});    // 不使用tree[0]
    size_t count; is >> count;
    for(size_t i = 0; i < count; ++i) {
        array<size_t, 2> a; is >> a[0] >> a[1];
        temp.push_back(a);
    }
    return tree = temp, is;
}

size_t get_depth(const tree_t &tree, size_t node, size_t init) {
    if(!node) return init;
    return ++init, max(get_depth(tree, tree[node][0], init), get_depth(tree, tree[node][1], init));
}

int main() {
    tree_t tree; cin >> tree;
    cout << get_depth(tree, 1, 0) << endl;
    return 0;
}

跳转到最佳答案楼层

傻眼貓咪

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

人造人

这个分数是怎么算的？

人造人

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

#include <iostream>
#include <vector>
#include <array>
#include <algorithm>

using std::vector, std::array;
using std::cin, std::cout, std::endl;
using std::istream;
using std::max;

using tree_t = vector<array<size_t, 2>>;

istream &operator>>(istream &is, tree_t &tree) {
    tree_t temp; temp.push_back({});    // 不使用tree[0]
    size_t count; is >> count;
    for(size_t i = 0; i < count; ++i) {
        array<size_t, 2> a;
        is >> a[0] >> a[1];
        temp.push_back(a);
    }
    return tree = temp, is;
}

size_t get_depth(const tree_t &tree, size_t node, size_t init) {
    if(!node) return init;
    return max(get_depth(tree, tree[node][0], init + 1), get_depth(tree, tree[node][1], init + 1));
}

int main() {
    tree_t tree; cin >> tree;
    cout << get_depth(tree, 1, 0) << endl;
    return 0;
}

人造人

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

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

人造人

稍微改一改

#include <iostream>
#include <vector>
#include <array>
#include <algorithm>

using std::vector, std::array;
using std::cin, std::cout, std::endl;
using std::istream;
using std::max;

using tree_t = vector<array<size_t, 2>>;

istream &operator>>(istream &is, tree_t &tree) {
    tree_t temp; temp.push_back({});    // 不使用tree[0]
    size_t count; is >> count;
    for(size_t i = 0; i < count; ++i) {
        array<size_t, 2> a; is >> a[0] >> a[1];
        temp.push_back(a);
    }
    return tree = temp, is;
}

size_t get_depth(const tree_t &tree, size_t node, size_t init) {
    if(!node) return init;
    return ++init, max(get_depth(tree, tree[node][0], init), get_depth(tree, tree[node][1], init));
}

int main() {
    tree_t tree; cin >> tree;
    cout << get_depth(tree, 1, 0) << endl;
    return 0;
}

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

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

7
5 7
4 6
0 0
0 0
2 0
0 0
0 3

人造人

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

这是3棵树吧？

人造人

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

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

人造人

7
5 7
4 6
0 0
0 0
2 0
0 0
0 3

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

人造人

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

#include <iostream>
#include <vector>
#include <array>
#include <algorithm>

using std::vector, std::array;
using std::cin, std::cout, std::endl;
using std::istream;
using std::max;

using tree_t = vector<array<size_t, 2>>;

istream &operator>>(istream &is, tree_t &tree) {
    tree_t temp; temp.push_back({});    // 不使用tree[0]
    size_t count; is >> count;
    for(size_t i = 0; i < count; ++i) {
        array<size_t, 2> a; is >> a[0] >> a[1];
        temp.push_back(a);
    }
    return tree = temp, is;
}

size_t get_depth(const tree_t &tree, size_t node) {
    if(!node) return 0;
    return max(get_depth(tree, tree[node][0]), get_depth(tree, tree[node][1])) + 1;
}

int main() {
    tree_t tree; cin >> tree;
    cout << get_depth(tree, 1) << endl;
    return 0;
}

柿子饼同学

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

#include <bits/stdc++.h>
using namespace std;

struct node{
        int lc, rc;
} tree[1000005];
int n, l, r, ans;

void dfs(int pos, int dep){
        if(!tree[pos].lc && !tree[pos].rc){
                ans = max(ans, dep);
        }
        if(tree[pos].lc) dfs(tree[pos].lc, dep + 1);
        if(tree[pos].rc) dfs(tree[pos].rc, dep + 1);
}

int main(){
        ios::sync_with_stdio(0);
        cin.tie(0);
        
        cin >> n;
        for(int i = 1; i <= n; i++){
                cin >> l >> r;
                tree[i] = {l, r};
        }

        dfs(1, 1);

        cout << ans ;
        
        return 0;
}

傻眼貓咪

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

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