递归
# 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]) -> TreeNode:
'''
前序遍历 [ 根节点, [左子树的前序遍历结果], [右子树的前序遍历结果] ]
中序遍历 [ [左子树的中序遍历结果], 根节点, [右子树的中序遍历结果] ]
根据前序遍历 可以得到 根节点
在中序遍历中定位根节点 可以得到树的左右节点数量
'''
# 使用dict 加速定位
inorder_dict = {item: i for i, item in enumerate(inorder)}
def build(pre_left_i, pre_right_i, in_left_i, in_right_i):
# 正常情况 left <= right
if pre_left_i > pre_right_i:
return None
# 前序的left 即为根
pre_root_i = pre_left_i
root_val = preorder[pre_root_i]
# 找到 中序遍历根节点的位置
in_root_i = inorder_dict[root_val]
# 根据中序遍历 计算左子树位置 不包含根节点
left_subtree_size = in_root_i - in_left_i
root = TreeNode(preorder[pre_root_i])
# 当前节点的左节点为 左子树的根节点
root.left = build(pre_left_i + 1, pre_left_i + left_subtree_size, in_left_i, in_root_i - 1)
# 同上 当前节点的右节点为 右子树的根节点
root.right = build(pre_left_i + left_subtree_size + 1, pre_right_i, in_root_i + 1, in_right_i)
# 返回根节点
return root
n = len(preorder)
return build(0, n - 1, 0, n - 1)
