本文共 1314 字，大约阅读时间需要 4 分钟。

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

例如，给出

前序遍历 preorder = [3,9,20,15,7]

限制：

0 <= 节点个数 <= 5000

来源：力扣（LeetCode）

分析

# Definition for a binary tree node.# class TreeNode:#     def __init__(self, x):#         self.val = x#         self.left = None#         self.right = Noneclass Solution:    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:        ##递归建树        def recursive(prel:int, prer:int, inl:int, inr:int) -> TreeNode:            if prel > prer:                return None            #建立根            root = TreeNode(preorder[prel])                        #找出目前根在inorder中的位置            i = hashtable[preorder[prel]]            #左右递归            root.left = recursive(prel+1, prel+i-inl, inl, i-1)            root.right = recursive(prel+i-inl+1, prer, i+1, inr)            return root                n = len(inorder)        #建立hashtable快速指出inorder中元素的索引        hashtable = {
   num : i for i,num in enumerate(inorder) }        return recursive(0, n-1, 0, n-1)

总结

转载地址：https://bridge-killer.blog.csdn.net/article/details/114974847 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！