编写一个程序,实现二叉树高度的求取。利用二叉树的性质及二叉树前序遍历的思想,计算二叉树的高度。
时间: 2023-11-14 14:15:39 浏览: 36
以下是 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)
# 返回左右子树高度的较大值加1
return max(left_height, right_height) + 1
# 测试
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.left = TreeNode(6)
root.right.right = TreeNode(7)
print(get_height(root)) # 输出 3
```
思路解析:
计算二叉树的高度,可以通过递归的方式来解决。对于每个节点,其高度等于其左右子树高度的较大值加1。因此我们可以先递归计算左右子树的高度,然后返回较大值加1即可。对于空节点,其高度为0。在代码实现中,我们可以定义一个 `TreeNode` 类来表示二叉树节点,然后再编写一个递归函数 `get_height` 来计算二叉树高度。最后,我们可以用一个例子来测试代码的正确性。