文章目录
- 题目要求
- 解题思路
- 递归
题目要求
输入某二叉树的前序遍历和中序遍历的结果,请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
解题思路
递归
- 根据前序遍历和中序遍历的特点生成二叉树。
- 使用字典存储中序遍历与其索引,降低查找的复杂度。
- 注意递归时传入的参数值。
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = Noneclass Solution(object):def buildTree(self, preorder, inorder):""":type preorder: List[int]:type inorder: List[int]:rtype: TreeNode"""def recursive(pre_l, pre_r, in_l, in_r):# 每次pre和in的长度是一样的,当pre_l == pre_r的时候只有一个元素,当pre_l > pre_r的时候,返回None。if pre_l > pre_r:return None# 查找根节点在中序遍历中的索引。root_index = dic[preorder[pre_l]]# 建立根节点。root = TreeNode(inorder[root_index])# 求出左子树的长度,便于后续操作。sizeofleft = root_index - in_l# 递归生成左子树。root.left = recursive(pre_l+1, pre_l+sizeofleft, in_l, root_index-1)# 递归生成右子树。root.right = recursive(pre_l+sizeofleft+1, pre_r, root_index+1, in_r)return root# 用字典储存中序遍历的索引,提高查找速度dic = {}for i in range(len(inorder)):dic[inorder[i]] = ireturn recursive(0, len(preorder)-1, 0, len(inorder)-1)










