LeetCode(python)——105.从前序与中序遍历序列构造二叉树

题目

给定两个整数数组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 <= 3000
• inorder.length == preorder.length
• -3000 <= preorder[i], inorder[i] <= 3000
• preorder和inorder均无重复元素
• inorder均出现在preorder
• preorder保证为二叉树的前序遍历序列
• inorder保证为二叉树的中序遍历序列

思路

1.前序序列——找根

2.中序序列——划分左右子树

3.递归遍历

具体步骤：
（1）递归结束条件：如果前序or中序序列为空，说明已遍历结束，return None

（2）创建根节点：取前序序列的第一个元素

（3）分左右子树：

• 在inorder中找根节点的索引值
• 根据这个索引值将preorder和inorder拆分成左右两个子树
• left_in = inorder[:root_index],right_in = inorder[root_index + 1:]
• left_pre = preorder[1:len(root_index) + 1],right_pre = preorder[len(root_index)+1,:]
• 递归处理左右子树

代码

# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]: if not preorder or not inorder: # 如果序列为空，return None return None root_val = preorder[0] # 取根节点 root = TreeNode(root_val) root_idx = inorder.index(root_val) # 在中序中找根节点索引 left_in = inorder[:root_idx] # 根据根节点索引划分左右子树 right_in = inorder[root_idx + 1:] left_pre = preorder[1: len(left_in) + 1] right_pre = preorder[len(left_in) + 1:] root.left = self.buildTree(left_pre, left_in) # 递归处理左右子树 root.right = self.buildTree(right_pre, right_in) return root