洛谷 题解 P4913 【【深基16.例3】二叉树深度】

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

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

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

\(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;//完结撒花！
}

洛谷 题解 P4913 【【深基16.例3】二叉树深度】

原文：https://www.cnblogs.com/zyh-cr7/p/12267105.html