自动搬运

查看原文

来自洛谷，原作者为

	zhangyuhan 陌上人如玉，公子世无双

搬运于2025-08-24 22:05:12，当前版本为作者最后更新于2020-02-05 22:43:07，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这是一道关于二叉树的入门题。

这题主要考察二叉树的存储以及二叉树的遍历。

那么我就来分这两部分来讲。

$Part$ $1$ 存储

考虑一个二叉树的每个节点都有两个子节点，所以我们可以考虑用一个结构体来存储：

struct node {
    int left, right;
};
node tree[MAXN];

其中，left和right分别代表节点的左节点编号和右节点编号。

当读入时，就非常方便了，直接读入即可：

_for (i, 1, n) cin >> tree[i].left >> tree[i].right;

$Part$ $2$ 遍历

这道题要我们求二叉树的深度，就一定要遍历这棵树。

首先明确一点题目中未提到的，编号为$1$的节点是二叉树的根节点。

于是我们可以从根节点出发，先递归遍历该节点的左节点，再递归遍历该节点的右节点。

其中还要记录该节点的深度，出发时深度为$1$

dfs(tree[id].left, deep+1);
dfs(tree[id].right, deep+1);

每到一个节点时更新一下深度：

ans = max(ans, deep);

到达叶子节点时，就return

if (id == 0) return ;

总体上就这么多吧。

因为每个节点遍历一次，所以总时间复杂度为$O(n)$

$AC$ $Code$

#include <iostream>
#define _for(i, a, b) for (int i=(a); i<=(b); i++)
using namespace std;

const int MAXN = 1e6 + 10;

struct node {
    int left, right;
};
node tree[MAXN];//存储结构定义

int n, ans;

void dfs(int id, int deep) {
    if (id == 0) return ;//到达叶子节点时返回
    ans = max(ans, deep);//更新答案
    dfs(tree[id].left, deep+1);//向左遍历
    dfs(tree[id].right, deep+1);//向右遍历
}

int main() {
    cin >> n;
    _for (i, 1, n) cin >> tree[i].left >> tree[i].right;//读入+建树
    dfs(1, 1);//从1号节点出发，当前深度为1
    cout << ans << endl;//输出答案
    return 0;//完结撒花！
}