若一棵树采用孩子链存储结构t存储,设计一个算法求其高度。实现算法python
时间: 2023-12-15 09:54:12 浏览: 31
以下是求解树的高度的 Python 代码,采用深度优先搜索(DFS)实现:
```python
class TreeNode:
def __init__(self, val, children=None):
self.val = val
self.children = children if children else []
def get_tree_height(root: TreeNode) -> int:
if not root:
return 0
max_height = 0
for child in root.children:
max_height = max(max_height, get_tree_height(child))
return max_height + 1
```
以上代码中,`TreeNode` 类表示树节点,其中 `val` 表示节点的值,`children` 表示该节点的子节点列表。`get_tree_height()` 函数接收根节点 `root` 作为参数,返回整棵树的高度。函数中采用递归的方式实现,对于每个节点,遍历其所有子节点,并求出每个子节点的高度,最终将其最大值加1,即为整棵树的高度。
使用示例:
```python
# 构造一棵树
root = TreeNode(1, [
TreeNode(2, [
TreeNode(4),
TreeNode(5, [
TreeNode(7)
])
]),
TreeNode(3, [
TreeNode(6)
])
])
# 求树的高度
height = get_tree_height(root)
print(height) # 4
```
以上示例中,构造了一棵树,根节点值为1,其它节点分别为2、3、4、5、6、7,树的高度为4。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![py](https://img-home.csdnimg.cn/images/20210720083646.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)