求二叉树的深度c++代码
时间: 2023-11-29 16:06:18 浏览: 43
二叉树的深度可以使用递归方法来实现,具体代码如下:
```c++
// 定义二叉树结点
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
int maxDepth(TreeNode* root) {
if (root == nullptr) {
return 0;
}
int leftDepth = maxDepth(root->left);
int rightDepth = maxDepth(root->right);
return max(leftDepth, rightDepth) + 1;
}
```
其中,`maxDepth()`函数用于计算二叉树的深度,参数`root`表示二叉树的根节点。如果根节点为空,则深度为0;否则,分别计算左子树和右子树的深度,取其中较大的值再加1,即为整棵树的深度。
相关问题
二叉树求深度c++
可以使用递归的方式来求二叉树的深度,具体实现如下:
```c++
// 定义二叉树节点结构体
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
int maxDepth(TreeNode* root) {
if (root == NULL) {
return 0;
}
int leftDepth = maxDepth(root->left); // 递归求左子树深度
int rightDepth = maxDepth(root->right); // 递归求右子树深度
return max(leftDepth, rightDepth) + 1; // 返回左右子树深度较大值加一
}
```
上述代码中,我们定义了一个 `maxDepth` 函数,它的输入参数是二叉树的根节点指针。如果根节点为空,说明二叉树为空树,深度为0,直接返回0。否则,我们分别递归求出左子树和右子树的深度,然后取左右子树深度的较大值,再加上1(加1是因为当前节点也要算一层),就是整个二叉树的深度。最后返回深度即可。
帮我用c++写一段求二叉树深度的代码
以下为使用C语言实现求二叉树深度的代码:
```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;
} else {
int leftDepth = maxDepth(root->left);
int rightDepth = maxDepth(root->right);
return (leftDepth > rightDepth ? leftDepth : rightDepth) + 1;
}
}
int main() {
// 构造一个二叉树
struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
root->val = 1;
struct TreeNode* node2 = (struct TreeNode*)malloc(sizeof(struct TreeNode));
node2->val = 2;
struct TreeNode* node3 = (struct TreeNode*)malloc(sizeof(struct TreeNode));
node3->val = 3;
struct TreeNode* node4 = (struct TreeNode*)malloc(sizeof(struct TreeNode));
node4->val = 4;
struct TreeNode* node5 = (struct TreeNode*)malloc(sizeof(struct TreeNode));
node5->val = 5;
root->left = node2;
root->right = node3;
node2->left = node4;
node2->right = NULL;
node3->left = NULL;
node3->right = node5;
node4->left = NULL;
node4->right = NULL;
node5->left = NULL;
node5->right = NULL;
// 求二叉树深度
int depth = maxDepth(root);
printf("The depth of the binary tree is: %d\n", depth);
// 释放内存
free(node5);
free(node4);
free(node3);
free(node2);
free(root);
return 0;
}
```
这里我们构造了一个二叉树,并使用`maxDepth`函数求出了其深度。其中,`maxDepth`函数采用递归的方式实现,对于每一个节点,我们分别计算其左子树和右子树的深度,并取两者中的较大值,最后加上1即为该节点所在子树的深度。如果该节点为空,则返回0。最终,整棵树的深度即为根节点的深度。