7-8 先序序列+中序序列建立二叉树python
时间: 2024-05-05 21:15:37 浏览: 8
以下是Python代码:
```
# 定义二叉树节点类
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
# 建立二叉树
def buildTree(preorder, inorder):
if not preorder or not inorder:
return None
# 前序遍历的第一个节点是根节点
root = TreeNode(preorder[0])
# 在中序遍历中找到根节点的位置
root_idx = inorder.index(preorder[0])
# 递归构建左子树和右子树
root.left = buildTree(preorder[1:root_idx+1], inorder[:root_idx])
root.right = buildTree(preorder[root_idx+1:], inorder[root_idx+1:])
return root
# 测试
preorder = [3, 9, 20, 15, 7]
inorder = [9, 3, 15, 20, 7]
root = buildTree(preorder, inorder)
# 输出树的中序遍历结果
def inorderTraversal(root):
if not root:
return []
res = []
res += inorderTraversal(root.left)
res.append(root.val)
res += inorderTraversal(root.right)
return res
print(inorderTraversal(root)) # [9, 3, 15, 20, 7]
```