用pythonj解决给定一棵二叉树的先序遍历序列和中序遍历序列,要求计算该二叉树的高度。
时间: 2024-05-01 07:18:54 浏览: 111
可以的,这是一个计算二叉树高度的常见问题。先根据先序遍历序列确定根节点,然后根据中序遍历序列确定左右子树。递归计算左右子树高度,取较大值加1即为该树的高度。代码实现可以参考以下示例:
```python
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
def buildTree(preorder, inorder):
if not preorder or not inorder:
return None
root_val = preorder[0]
root = TreeNode(root_val)
root_index = inorder.index(root_val)
root.left = buildTree(preorder[1:root_index+1], inorder[:root_index])
root.right = buildTree(preorder[root_index+1:], inorder[root_index+1:])
return root
def getHeight(root):
if not root:
return 0
left_height = getHeight(root.left)
right_height = getHeight(root.right)
return max(left_height, right_height) + 1
preorder = [1, 2, 4, 5, 3, 6]
inorder = [4, 2, 5, 1, 3, 6]
root = buildTree(preorder, inorder)
print(getHeight(root)) # output: 3
```
阅读全文