题意概括

给定一个二叉树，找出其最大深度。最大深度被定义为从根节点到最远叶子节点的最长路径上的 节点数。

输入格式:

• 输入包含多组测试数据。
• 每组数据首先是一个整数 n，表示层序遍历序列中的节点总数（包括空节点）。
• 接下来一行是 n 个整数，表示树的层序遍历，其中 -1 代表空节点。

输出格式:

• 对于每组测试数据，输出一个整数，即二叉树的最大深度。

基础知识

计算二叉树的最大深度是一个基础的树遍历问题，可以通过 深度优先搜索 (DFS) 或 广度优先搜索 (BFS) 解决。这里介绍更为简洁的 DFS 递归解法。

二叉树的深度天然具有递归的结构：

1. 基本情况 (Base Case)：如果一个节点为空（空树），那么它的深度为 0。
2. 递归关系 (Recursive Step)：如果一个节点非空，它的深度等于其左、右子树深度的较大值，再加上 1（节点本身）。

我们可以用数学公式表达这个关系，令 $D(u)$ 表示以节点 $u$ 为根的子树的深度：

$$D(u) = \begin{cases} 0 & \text{if } u \text{ is null} \\ 1 + \max(D(u.\text{left}), D(u.\text{right})) & \text{otherwise} \end{cases} $$

这个公式可以直接转化为一个递归函数。我们首先需要根据输入的层序遍历序列构建树的结构，然后从根节点开始调用这个递归函数即可得到整棵树的最大深度。

该算法的时间复杂度为 $O(N)$，因为我们需要访问每个节点一次来构建树和计算深度。空间复杂度为 $O(H)$，其中 $H$ 是树的高度，主要由递归栈的深度决定，最坏情况下为 $O(N)$。

#include<bits/stdc++.h>

using namespace std;
using ll=long long;

// 节点结构体
struct Nde {
    int v;
    Nde *l, *r;
    Nde(int val) : v(val), l(nullptr), r(nullptr) {}
};

// DFS递归计算最大深度
int dfs(Nde* u) {
    if (!u) {
        return 0; // 空树深度为0
    }
    // 深度 = 1 + max(左子树深度, 右子树深度)
    return 1 + max(dfs(u->l), dfs(u->r));
}

void run(int n) {
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    
    if (n == 0 || a[0] == -1) {
        cout << 0 << endl;
        return;
    }

    // 使用队列通过层序遍历结果建树
    Nde* rt = new Nde(a[0]);
    queue<Nde*> q;
    q.push(rt);

    int i = 1;
    while (!q.empty() && i < n) {
        Nde* cur = q.front();
        q.pop();

        // 处理左孩子
        if (i < n && a[i] != -1) {
            cur->l = new Nde(a[i]);
            q.push(cur->l);
        }
        i++;

        // 处理右孩子
        if (i < n && a[i] != -1) {
            cur->r = new Nde(a[i]);
            q.push(cur->r);
        }
        i++;
    }

    cout << dfs(rt) << endl;
    
}

int main() {
    // 关闭同步流
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n;
    // 处理多组测试数据
    while (cin >> n) {
        run(n);
    }

    return 0;
}

/*
样例 1:
输入:
7
3 9 20 -1 -1 15 7
输出:
3

样例 2:
输入:
3
1 -1 2
(修正: n应为3)
输出:
2

样例 3:
输入:
1
-1
输出:
0
*/