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

傻眼貓咪

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

好像也是

zhangjinxuan

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

只想说这个思路对不对？

人造人

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

看17楼

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

复制代码

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

傻眼貓咪

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

傻眼貓咪

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

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

1. #include <iostream>
   
2. #include <vector>
   
3. #include <utility>
   
4. 
   
5. using std::vector, std::pair;
   
6. vector <pair <unsigned, unsigned>> trees;
   
7. auto max = [](unsigned a, unsigned b) -> unsigned { return a > b ? a : b; };
   
8. 
   
9. int Dijkstra(unsigned left, unsigned right, unsigned levels = 0) {
   
10.         return not(left) and not(right) ? levels : // 左右叶为 0，此为这支根的最深层，返回层数
    
11.                 not(left) ? Dijkstra(trees[right].first, trees[right].second, levels + 1) : // 左叶为 0
    
12.                 not(right) ? Dijkstra(trees[left].first, trees[left].second, levels + 1) : // 右叶为 0
    
13.                 max(
    
14.                         Dijkstra(trees[left].first, trees[left].second, levels + 1),
    
15.                         Dijkstra(trees[right].first, trees[right].second, levels + 1)); // 比较左右叶节点深度，返回最深层层数
    
16. }
    
17. 
    
18. using std::cout, std::cin, std::endl;
    
19. using std::make_pair;
    
20. int main(void) {
    
21.         unsigned n, l, r;
    
22.         int ans = -(1 << 30);
    
23.         trees.push_back(make_pair(0, 0));
    
24.         cin >> n;
    
25.         while (n--) {
    
26.                 cin >> l >> r;
    
27.                 trees.push_back(make_pair(l, r));
    
28.         }
    
29.         ans = Dijkstra(1, 1);
    
30.         cout << ans << endl;
    
31.         return 0;
    
32. }

复制代码