二叉树的高度
时间: 2023-11-14 18:17:55 浏览: 38
二叉树的高度是指从根节点到最远叶子节点的距离(边数)。
可以使用递归的方式求解二叉树的高度,如果树为空,返回0;否则,分别递归求解左子树和右子树的高度,取两者中的较大值,并加上根节点到其子树的距离1,即可得到整棵树的高度。
下面是求解二叉树高度的示例代码:
```
int height(Node* root) {
if (root == NULL) return 0;
int left_height = height(root->left);
int right_height = height(root->right);
return 1 + max(left_height, right_height);
}
```
相关问题
二叉树高度计算
计算二叉树的高度可以使用递归的方法。先判断二叉树是否为空,为空则高度为0。如果不为空,则递归计算左子树和右子树的高度,然后取左右子树高度的最大值并加1(加1是因为要算上根节点),即为整个二叉树的高度。
以下是示例代码:
```
int getHeight(TreeNode* root) {
if (!root) { // 如果二叉树为空,高度为0
return 0;
}
int leftHeight = getHeight(root->left); // 计算左子树高度
int rightHeight = getHeight(root->right); // 计算右子树高度
return max(leftHeight, rightHeight) + 1; // 取左右子树高度的最大值并加1
}
```
其中,TreeNode 是二叉树节点的定义。左子树和右子树的高度也是用递归的方式计算的,因此可以使用同样的方法来实现。
编写求二叉树高度的函数
好的,以下是求二叉树高度的函数的Python代码实现:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def get_height(root):
if not root:
return 0
left_height = get_height(root.left)
right_height = get_height(root.right)
return max(left_height, right_height) + 1
```
其中,`TreeNode`为二叉树节点的类定义,`get_height`为求二叉树高度的函数,`root`为根节点。函数的实现采用递归的方式,分别计算左子树和右子树的高度,取两者中的较大值并加上1即为整棵树的高度。如果根节点为空,则返回0。