洛谷题单指南-二叉树-P4913 【深基16.例3】二叉树深度

原题链接：https://www.luogu.com.cn/problem/P4913

题意解读：计算二叉树的深度

解题思路：

首先介绍二叉树的存储方式，对于本题，直接用数组模拟，数组的下标即节点号

struct node
{
    int l, r;
} tree[N];

tree[i].l存的是节点i的左子结点，tree[i].r存的是节点i的右子节点。

计算深度至少有三种方法：递归、DFS、BFS，下面主要介绍前两种方法：

1、递归

从二叉树深度的定义出发，给定一个根节点，根节点以下的最大深度等于左子树的最大深度、右子树的最大深度中较大者，

树的深度再加1即可，用递归的定义就是：

  depth(root) = max(depth(root->left), depth(root->right)) + 1

100分代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 5;

struct node
{
    int l, r;
} tree[N];

int n;

int depth(int root)
{
    if(root == 0) return 0;
    return max(depth(tree[root].l), depth(tree[root].r)) + 1;
}

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> tree[i].l >> tree[i].r;
    }
    cout << depth(1);

    return 0;
}

 2、DFS

从根节点出发，针对左、右子节点进行DFS，每DFS递归调用一次，深度都+1，记录这个过程中深度最大值即可。

100分代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 5;

struct node
{
    int l, r;
} tree[N];

int ans, n;

void dfs(int root, int depth)
{
    if(root == 0) return;
    ans = max(ans, depth);
    dfs(tree[root].l, depth + 1);
    dfs(tree[root].r, depth + 1);
}

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> tree[i].l >> tree[i].r;
    }
    dfs(1, 1);
    cout << ans;
    return 0;
}