写一个代码根据二叉树的前序和中序输出一个二叉树
时间: 2024-09-13 08:13:13 浏览: 39
Python实现二叉树前序、中序、后序及层次遍历示例代码
5星 · 资源好评率100%
当然可以。在计算机科学中,给定一棵二叉树的前序遍历(根节点 -> 左子树 -> 右子树)和中序遍历(左子树 -> 根节点 -> 右子树),我们可以重建这棵树。这是一个常见的算法题目,通常通过递归实现。这里是一个Python的例子:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def buildTree(preorder, inorder):
if not preorder or not inorder:
return None
root_val = preorder[0]
root = TreeNode(root_val)
# 找到root在inorder序列中的索引
index = inorder.index(root_val)
# 使用中序序列构建左子树和右子树
root.left = buildTree(preorder[1:index+1], inorder[:index])
root.right = buildTree(preorder[index+1:], inorder[index+1:])
return root
# 示例:前序遍历 [3,9,20,15,7],中序遍历 [9,3,15,20,7]
preorder = [3, 9, 20, 15, 7]
inorder = [9, 3, 15, 20, 7]
tree = buildTree(preorder, inorder)
```
这个函数首先找到前序遍历的第一个元素,作为当前根节点。然后在中序遍历中找到该节点的位置,接着分别递归地构建左右子树。如果你想要测试或者有更多的问题,请告诉我。
阅读全文