二叉树求最大深度,C++
时间: 2023-06-27 16:02:48 浏览: 53
下面是一个递归的实现:
```cpp
class Solution {
public:
int maxDepth(TreeNode* root) {
if (root == nullptr) {
return 0;
}
int left_depth = maxDepth(root->left);
int right_depth = maxDepth(root->right);
return max(left_depth, right_depth) + 1;
}
};
```
其中,`TreeNode` 表示二叉树节点的结构体,定义如下:
```cpp
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
```
该方法的时间复杂度为 $O(n)$,其中 $n$ 是二叉树的节点数。
相关问题
二叉树的最大深度c++
二叉树的最大深度可以通过递归实现。具体实现方式如下:
```c++
class TreeNode {
public:
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;否则,分别递归计算左子树和右子树的最大深度,并取两者中的较大值加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是因为当前节点也要算一层),就是整个二叉树的深度。最后返回深度即可。