二叉树求深度c++
时间: 2023-07-19 16:17:55 浏览: 56
可以使用递归的方式来求二叉树的深度,具体实现如下:
```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++代码实现:
1. 创建一个二叉树
```c++
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
TreeNode* createTree() {
int val;
cin >> val;
if (val == -1) {
return NULL;
}
TreeNode* root = new TreeNode(val);
root->left = createTree();
root->right = createTree();
return root;
}
```
2. 二叉树的遍历(前序遍历、中序遍历、后序遍历)
```c++
// 前序遍历
void preorderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
cout << root->val << " ";
preorderTraversal(root->left);
preorderTraversal(root->right);
}
// 中序遍历
void inorderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
inorderTraversal(root->left);
cout << root->val << " ";
inorderTraversal(root->right);
}
// 后序遍历
void postorderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
postorderTraversal(root->left);
postorderTraversal(root->right);
cout << root->val << " ";
}
```
3. 求二叉树的深度
```c++
int maxDepth(TreeNode* root) {
if (root == NULL) {
return 0;
}
int leftDepth = maxDepth(root->left);
int rightDepth = maxDepth(root->right);
return max(leftDepth, rightDepth) + 1;
}
```
4. 判断是否为平衡二叉树
```c++
bool isBalanced(TreeNode* root) {
if (root == NULL) {
return true;
}
int leftDepth = maxDepth(root->left);
int rightDepth = maxDepth(root->right);
if (abs(leftDepth - rightDepth) > 1) {
return false;
}
return isBalanced(root->left) && isBalanced(root->right);
}
```
5. 判断是否为对称二叉树
```c++
bool isSymmetric(TreeNode* root) {
if (root == NULL) {
return true;
}
return isSymmetricHelper(root->left, root->right);
}
bool isSymmetricHelper(TreeNode* leftNode, TreeNode* rightNode) {
if (leftNode == NULL && rightNode == NULL) {
return true;
}
if (leftNode == NULL || rightNode == NULL) {
return false;
}
if (leftNode->val != rightNode->val) {
return false;
}
return isSymmetricHelper(leftNode->left, rightNode->right)
&& isSymmetricHelper(leftNode->right, rightNode->left);
}
```
求二叉树的深度c++代码
二叉树的深度可以使用递归方法来实现,具体代码如下:
```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,即为整棵树的深度。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)