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

傻眼貓咪

人造人 发表于 2022-10-27 23:48
题目没有说把二叉树建立成什么形式
我想直接在数组中保存结点的形式也是可以的

好像也是

zhangjinxuan

柿子饼同学 发表于 2022-10-28 17:30

只想说这个思路对不对？

人造人

傻眼貓咪 发表于 2022-10-28 19:18
应该是没有问题，因为可以得到 80 分，我猜可能不完善吧，或是像人造人大佬说的那样，不够优雅吧

看17楼

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

这组输入，应该输出4，他的程序输出的是3

傻眼貓咪

人造人 发表于 2022-10-28 19:48
看17楼

傻眼貓咪

人造人 发表于 2022-10-28 19:48
看17楼

我试试写了代码练习练习：

#include <iostream>
#include <vector>
#include <utility>

using std::vector, std::pair;
vector <pair <unsigned, unsigned>> trees;
auto max = [](unsigned a, unsigned b) -> unsigned { return a > b ? a : b; };

int Dijkstra(unsigned left, unsigned right, unsigned levels = 0) {
        return not(left) and not(right) ? levels : // 左右叶为 0，此为这支根的最深层，返回层数
                not(left) ? Dijkstra(trees[right].first, trees[right].second, levels + 1) : // 左叶为 0
                not(right) ? Dijkstra(trees[left].first, trees[left].second, levels + 1) : // 右叶为 0
                max(
                        Dijkstra(trees[left].first, trees[left].second, levels + 1),
                        Dijkstra(trees[right].first, trees[right].second, levels + 1)); // 比较左右叶节点深度，返回最深层层数
}

using std::cout, std::cin, std::endl;
using std::make_pair;
int main(void) {
        unsigned n, l, r;
        int ans = -(1 << 30);
        trees.push_back(make_pair(0, 0));
        cin >> n;
        while (n--) {
                cin >> l >> r;
                trees.push_back(make_pair(l, r));
        }
        ans = Dijkstra(1, 1);
        cout << ans << endl;
        return 0;
}