力扣105-从前序与中序遍历序列构造二叉树

105. 从前序与中序遍历序列构造二叉树 - 力扣LeetCode给定两个整数数组preorder和inorder其中preorder是二叉树的先序遍历inorder是同一棵树的中序遍历请构造二叉树并返回其根节点。示例 1:输入**:preorder [3,9,20,15,7], inorder [9,3,15,20,7]输出:** [3,9,20,null,null,15,7]示例 2:输入:preorder [-1], inorder [-1]输出:[-1]提示:1 preorder.length 3000inorder.length preorder.length-3000 preorder[i], inorder[i] 3000preorder和inorder均无重复元素inorder均出现在preorderpreorder保证为二叉树的前序遍历序列inorder保证为二叉树的中序遍历序列方法一递归本题的一个关键信息是两个序列中均没有重复元素前序遍历的第一个元素必然是根节点因此我们可以在中序遍历序列中定位到根节点的位置。而中序遍历的结果必然是左子树的中序遍历序列、根节点、右子树的中序遍历序列又根据中序遍历与前序遍历的序列长度相同所以可得左右子树的前序/中序遍历序列使用递归构造出左子树和右子树再把两棵子树的根节点接到整棵树根节点的左右两边即可注意到一个问题每次递归都要先根据前序遍历序列找到根节点然后去定位其在中序遍历序列中的位置这个过程是 O(n) 的我们可以在开始构造之前用一个哈希表记录一个节点在中序遍历序列中的出现位置。即key 是这个节点的值因为唯一value 是这个节点在中序遍历序列中出现的位置。这样一来只需要遍历一趟中序遍历序列后续的递归中都只需要 O(1) 的时间对根节点进行定位class Solution: def buildTree(self, preorder: List[int], inorder: List[int]) - Optional[TreeNode]: def func(preorder_left: int, preorder_right: int, inorder_left: int, inorder_right: int): # 递归终止条件 if preorder_left preorder_right: return None # 前序遍历的第一个节点就是根节点 root_pre preorder_left # 构建根节点 root TreeNode(preorder[root_pre]) # 在中序遍历中定位根节点下标 inorder_root index[preorder[root_pre]] # 左子树中根节点数目 left_subTree_size inorder_root - inorder_left # 递归地构造左子树左子树的前序遍历序列是 preorder 从下标1开始往后找 left_subTree_size 个数目构成的序列 root.left func(preorder_left 1, preorder_left left_subTree_size, inorder_left, inorder_root - 1) # 右子树同理 root.right func(preorder_left left_subTree_size 1, preorder_right, inorder_root 1, inorder_right) return root n len(preorder) index {element: i for i, element in enumerate(inorder)} return func(0, n - 1, 0, n - 1)