求二叉树深度，为什么只有80分
本帖最后由 zhangjinxuan 于 2022-11-4 21:35 编辑描述和格式见后面的图片
输入样例：
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, d, x, y, ans = -(1 << 30);
int main() {
scanf("%d", &n);
d = 1;
for (int i = 1; i <= n; ++i) {
scanf("%d%d", &x, &y);
if (x) ans = max(d = d + 1, ans);
if (y) ans = max(d = d + 1, ans);
}
printf("%d", ans);
} 题目要求建立一个二叉树，至少要有二叉树构造吧？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
size_t count; is >> count;
for(size_t i = 0; i < count; ++i) {
array<size_t, 2> a;
is >> a >> a;
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, init + 1), get_depth(tree, tree, 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
size_t count; is >> count;
for(size_t i = 0; i < count; ++i) {
array<size_t, 2> a; is >> a >> a;
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, init), get_depth(tree, tree, init));
}
int main() {
tree_t tree; cin >> tree;
cout << get_depth(tree, 1, 0) << endl;
return 0;
}
人造人 发表于 2022-10-27 23:52
稍微改一改
我只是想说，我的这个代码有没有问题 傻眼貓咪 发表于 2022-10-27 22:50
题目要求建立一个二叉树，至少要有二叉树构造吧？class 或 struct
我的代码有问题吗？ zhangjinxuan 发表于 2022-10-28 07:35
我只是想说，我的这个代码有没有问题
https://fishc.com.cn/forum.php?mod=redirect&goto=findpost&ptid=220003&pid=6029054
不知道对不对，"""多给几组输入/输出看看"""
https://fishc.com.cn/forum.php?mod=redirect&goto=findpost&ptid=220003&pid=6029011
""" 这个分数是怎么算的？"""
分数怎么算的？也许就是因为你的代码写的不够优雅，扣了你20分
多给几组输入/输出看看
就一组输入/输出看不出问题
还有，在哪组输入/输出上面出了问题？
你的刷题网站不显示出问题的输入/输出？
我的回复都是有用的，你的看我的回复
我问你的问题就是你提问题的时候漏掉的那部分
没有你漏掉的那部分，问题就很不好解决
zhangjinxuan 发表于 2022-10-28 07:35
我的代码有问题吗？
有肯定是有，首先的第一个问题就是你的代码写的不够优雅
要我做裁判，凭这一点就扣你20分不行吗？
^_^
确实在我看来，问题不是对就是错，不是0分就是100分
如果你非要细分的话，那就是在答案正确的前提下，看你代码写的怎么样
所以我要问你计分规则是怎么样的，因为在我看来就是上面说到的那样
代码写的不够优雅，扣20分
^_^
zhangjinxuan 发表于 2022-10-28 07:35
我只是想说，我的这个代码有没有问题
可是我想知道我的代码有没有问题
本帖最后由 人造人 于 2022-10-28 10:28 编辑
知道吗？一个不能重现的问题基本无解
如果知道了出问题的那组输入/输出
可以非常容易的找出代码中的问题
用调试器把程序运行起来，输入出问题的那个输入数据，一行代码一行代码的执行，看执行结果，如果执行结果即将脱离正确答案的那条路径
那问题就在这里了，如果是函数调用，那就重新运行程序，一样的输入，在这个函数的时候跟进去，一样的方法，看看哪行代码脱离了正确答案
调试程序是作为程序员的必备技能，同意吗？同意吧？
考虑这组输入，应该不是能产生问题的最小输入，但是也比较小好分析了
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
size_t count; is >> count;
for(size_t i = 0; i < count; ++i) {
array<size_t, 2> a; is >> a >> a;
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), get_depth(tree, tree)) + 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;
int n, l, r, ans;
void dfs(int pos, int dep){
if(!tree.lc && !tree.rc){
ans = max(ans, dep);
}
if(tree.lc) dfs(tree.lc, dep + 1);
if(tree.rc) dfs(tree.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 = {l, r};
}
dfs(1, 1);
cout << ans ;
return 0;
}
zhangjinxuan 发表于 2022-10-28 07:35
我的代码有问题吗？
应该是没有问题，因为可以得到 80 分，我猜可能不完善吧，或是像人造人大佬说的那样，不够优雅吧{:5_99:}
页:
[1]
2