写一个求树的最大深度的c++代码
时间: 2023-02-23 21:06:33 浏览: 64
以下是一个求二叉树最大深度的C语言代码示例:
```
#include<stdio.h>
#include<stdlib.h>
// 定义二叉树的节点结构
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
int maxDepth(struct TreeNode* root) {
if (root == NULL) {
return 0;
}
int left_depth = maxDepth(root->left);
int right_depth = maxDepth(root->right);
return (left_depth > right_depth ? left_depth : right_depth) + 1;
}
int main() {
return 0;
}
```
这是一个递归的方法,它在二叉树的每个节点上递归地求最大深度,其中 `maxDepth` 函数递归地计算以该节点为根节点的子树的最大深度,然后返回左右子树中较大的那一个加上 1(因为当前节点深度为 1)。
相关问题
用c++代码计算一棵树的深度
如果使用C语言计算一棵树的深度,可以使用递归函数来计算树的最大深度。具体的实现方法可以参考下面的代码:int maxDepth(struct node* node)
{
if (node==NULL)
return 0;
else
{
/* compute the depth of each subtree */
int lDepth = maxDepth(node->left);
int rDepth = maxDepth(node->right);
/* use the larger one */
if (lDepth > rDepth)
return(lDepth+1);
else return(rDepth+1);
}
}
树的深度c++
树的深度可以使用深度优先搜索(DFS)或广度优先搜索(BFS)来求解。以下是使用DFS的C++代码示例:
```c++
#include <iostream>
#include <vector>
using namespace std;
int max_depth = 0;
void dfs(vector<int> adj[], int u, int depth) {
max_depth = max(max_depth, depth);
for(int v : adj[u]) {
dfs(adj, v, depth + 1);
}
}
int main() {
int n, m;
cin >> n >> m;
vector<int> adj[n + 1];
for(int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
dfs(adj, 1, 1);
cout << max_depth << endl;
return 0;
}
```
其中,`adj`是邻接表表示的树,`max_depth`表示最大深度,`dfs`是DFS函数,`u`是当前节点,`depth`是当前深度。在`dfs`函数中,遍历当前节点的所有子节点,更新最大深度,并递归遍历子节点。在主函数中,读入树,调用`dfs`函数求解最大深度。