用c++编写函数,求树的深度
时间: 2024-02-18 07:02:22 浏览: 23
可以使用递归的方式求解树的深度,具体实现如下:
```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;
}
```
该函数的作用是求解以 `root` 为根节点的树的深度。如果 `root` 为空,则深度为 0;否则,深度等于左子树深度和右子树深度的较大值加 1。其中,左子树深度和右子树深度可以通过递归的方式求解。
示例:
```c++
TreeNode* root = new TreeNode(3);
root->left = new TreeNode(9);
root->right = new TreeNode(20);
root->right->left = new TreeNode(15);
root->right->right = new TreeNode(7);
cout << maxDepth(root) << endl; // 输出 3
```
该示例中,树的结构如下:
```
3
/ \
9 20
/ \
15 7
```
因此,树的深度为 3。