编写递归算法:求二叉树的高度。
时间: 2024-01-23 20:40:17 浏览: 55
递归算法求二叉树的高度可以通过以下步骤实现:
1. 如果二叉树为空,返回0作为高度。
2. 否则,递归地计算左子树和右子树的高度,并将其较大值加1作为二叉树的高度返回。
以下是递归算法的Python代码实现:
```python
def tree_height(root):
if root is None:
return 0
else:
left_height = tree_height(root.left)
right_height = tree_height(root.right)
return max(left_height, right_height) + 1
```
其中,`root`是二叉树的根节点。如果二叉树为空,则返回0。否则,递归计算左子树和右子树的高度,并将其较大值加1作为二叉树的高度返回。
相关问题
在python语言中,编写递归算法:求二叉树的高度
可以使用以下代码实现:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def tree_height(root: TreeNode) -> int:
if not root:
return 0
left_height = tree_height(root.left)
right_height = tree_height(root.right)
return max(left_height, right_height) + 1
```
其中,`TreeNode` 为二叉树节点的定义,包含一个值 `val` 和左右子节点 `left` 和 `right`。`tree_height` 函数为递归函数,用于求二叉树的高度。如果节点为空,返回高度为0;否则,分别求出左子树和右子树的高度,取二者中的最大值加1即为该节点所在子树的高度。最终返回根节点所在子树的高度即可。
编写算法求二叉树高度
编写算法求二叉树的高度可以使用递归的方式来实现。下面是一个示例算法:
1. 如果二叉树为空,则返回0。
2. 否则,递归计算左子树的高度,记为left_height。
3. 递归计算右子树的高度,记为right_height。
4. 返回左子树高度和右子树高度中的较大值加1。
以下是示例代码实现:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def get_tree_height(root):
if root is None:
return 0
else:
left_height = get_tree_height(root.left)
right_height = get_tree_height(root.right)
return max(left_height, right_height) + 1
```
相关推荐
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![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)