4.13每日一题之二叉树深度

大家好哇，我是一勺黑猫。

今天是每日一题的第十三天，欢迎更多小伙伴加入到我们的打卡计划中，希望和你们在学习算法的路上一起进步~

🙎作者简介：一个正在努力学算法和后端的大三girl

⏳每日一题打卡地：高校算法学习社区

🎈联系方式：157543570(qq)

💨往期内容：

黑猫的每日一题https://blog.csdn.net/xingziyy/category_11731303.html

P4913 【深基16.例3】二叉树深度 - 洛谷 | 计算机科学教育新生态

🌰思路：二叉树的深度是老生常谈的问题了。

如果根节点不为空，那这个树的深度就是1+max(左子树深度, 右子树深度)，如下图：

 二叉树如果是由链表形式给出的，我们通常构造这样的结构体：

struct TreeNode{
    int val;
    TreeNode *left,*right;
};

可以很容易写出二叉树深度递归的代码：

int dfs(TreeNode *root){
    if(root==NULL)
        return 0;
    return 1+max(dfs(root->left),dfs(root->right));
}

而本题的输入形式，每个节点的序号可以和数组下标一一对应，并不需要创建链表，只需存储左右子树的序号，这样left域和right域的类型用int就可以了。

具体代码如下。

🌰AC代码：

#include
#include
using namespace std;

struct TreeNode{
    int left,right;
};

vector v;    //存储二叉树的每个节点

int dfs(int root){

    //根节点为0时说明是空节点，深度为0
    if(root==0)
        return 0;

    //返回根节点的深度1+左右子树的最大深度
    return 1+max(dfs(v[root].left),dfs(v[root].right));
}

int main(){
    int n;
    cin>>n;
    v.resize(n+1);
    for(int i=1;i<=n;i++)
        cin>>v[i].left>>v[i].right;
    cout<