7-2 还原二叉树python
时间: 2023-10-28 11:02:51 浏览: 84
还原二叉树是指根据二叉树的前序遍历和中序遍历结果,重建出原二叉树的过程。实现这个过程的关键是找到二叉树的根节点,然后再根据根节点将左子树和右子树递归地还原。
首先,我们需要定义一个二叉树节点的类,包含节点值、左孩子节点和右孩子节点的属性。接下来,我们可以使用递归的方法来还原二叉树。
我们可以利用前序遍历的结果,找到二叉树的根节点。前序遍历结果的第一个元素就是根节点的值。然后,我们可以在中序遍历结果中找到根节点的位置,将中序遍历结果分为左子树和右子树的部分。
接下来,对于根节点的左子树,我们可以用前序遍历结果和中序遍历结果的左子树部分递归地还原左子树。同理,对于根节点的右子树,我们可以用前序遍历结果和中序遍历结果的右子树部分递归地还原右子树。
最后,我们将根节点的左子树和右子树连接到根节点上,就可以得到还原后的二叉树。
下面是一个简单的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_index = inorder.index(root_val)
left_inorder = inorder[:root_index]
right_inorder = inorder[root_index+1:]
# 递归还原左子树和右子树
left_preorder = preorder[1:1+len(left_inorder)]
right_preorder = preorder[1+len(left_inorder):]
root.left = buildTree(left_preorder, left_inorder)
root.right = buildTree(right_preorder, right_inorder)
return root
# 测试
preorder = [1, 2, 4, 5, 3, 6, 7]
inorder = [4, 2, 5, 1, 6, 3, 7]
root = buildTree(preorder, inorder)
```
以上是还原二叉树的简单实现。这个方法的时间复杂度为O(n),其中n是二叉树节点的个数。