还原二叉树python
时间: 2023-11-27 07:45:10 浏览: 35
还原二叉树是指根据给定的遍历结果,重建出原来的二叉树。在Python中,可以使用链式存储的方式来实现二叉树的还原。具体实现方法可以参考以下步骤:
1. 定义一个二叉树节点类,包含节点值、左子树和右子树三个属性。
2. 根据给定的遍历结果,确定二叉树的根节点。
3. 根据根节点在中序遍历结果中的位置,将遍历结果分为左子树和右子树两部分。
4. 递归地对左子树和右子树进行还原,得到左子树和右子树的根节点,并将其作为当前节点的左子树和右子树。
5. 返回根节点。
以下是一个简单的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_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
```