重建二叉树的详细解题思路
时间: 2023-11-29 07:57:32 浏览: 105
还原二叉树
重建二叉树是一道经典的二叉树问题,其解题思路如下:
1. 首先,我们需要根据前序遍历序列和中序遍历序列来重建二叉树。前序遍历序列的第一个节点一定是二叉树的根节点,中序遍历序列中根节点左边的所有节点都属于二叉树的左子树,右边的所有节点都属于二叉树的右子树。
2. 我们可以通过前序遍历序列找到二叉树的根节点,然后在中序遍历序列中找到根节点的位置。根节点左边的所有节点都属于左子树,右边的所有节点都属于右子树。
3. 接下来,我们递归构建左子树和右子树。我们可以根据前序遍历序列和中序遍历序列中左右子树的节点数量确定左右子树的范围。
4. 重复以上步骤,直到遍历完整个序列,最终得到重建的二叉树。
下面是重建二叉树的代码实现,代码注释中有详细的解释。
```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):
"""
:type preorder: List[int]
:type inorder: List[int]
:rtype: TreeNode
"""
# 如果前序遍历序列和中序遍历序列为空,返回None
if not preorder or not inorder:
return None
# 前序遍历序列的第一个节点一定是二叉树的根节点
root_val = preorder[0]
root = TreeNode(root_val)
# 在中序遍历序列中找到根节点的位置
root_index = inorder.index(root_val)
# 递归构建左子树和右子树
left_preorder = preorder[1:root_index+1]
left_inorder = inorder[:root_index]
left = buildTree(left_preorder, left_inorder)
right_preorder = preorder[root_index+1:]
right_inorder = inorder[root_index+1:]
right = buildTree(right_preorder, right_inorder)
# 将左右子树连接到根节点上
root.left = left
root.right = right
return root
```
以上就是重建二叉树的详细解题思路和代码实现。
阅读全文