leetcode 剑指 Offer 07. 重建二叉树

   声明:本站部分内容来自互联网,如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。

25

文章目录

    • 题目要求
    • 解题思路
      • 递归

题目要求

输入某二叉树的前序遍历和中序遍历的结果,请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

解题思路

递归

  1. 根据前序遍历和中序遍历的特点生成二叉树。
  2. 使用字典存储中序遍历与其索引,降低查找的复杂度。
  3. 注意递归时传入的参数值。
# 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)