4.13每日一题之二叉树深度(洛谷c++)|dfs遍历树

article/2025/11/11 0:22:06

🍄前言

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

🙎作者简介：一个正在努力学算法和后端的大三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<iostream>
#include<vector>
using namespace std;struct TreeNode{int left,right;
};vector<TreeNode> v;    //存储二叉树的每个节点int dfs(int root){//根节点为0时说明是空节点，深度为0if(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<<dfs(1);return 0;
}