[数据结构与算法]【leetcode】105. 从前序与中序遍历序列构造二叉树（中等）

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 保证 为二叉树的中序遍历序列

思路&代码

已知先序和中序遍历画二叉树，学过数据结构的基本都会，不太了解的可以参考一下已知二叉树的先序遍历和中序遍历画出该二叉树或者自己上网查查学一下。

# 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:
        def fun(preorder_op, preorder_ed, inorder_op, inorder_ed):
            if preorder_op > preorder_ed:
                return None
            val_root = preorder[preorder_op]
            loc_root = inorder.index(val_root)
            num_left = loc_root - inorder_op
            num_right = inorder_ed - loc_root

            root = TreeNode(val=val_root)
            root.left = fun(preorder_op+1, preorder_op+num_left, inorder_op, inorder_op+num_left-1)
            # preorder_op+num_left实际上是(preorder_op+1)+(num_left-1)
            root.right = fun(preorder_ed-num_right+1, preorder_ed, inorder_ed-num_right+1, inorder_ed)
            return root
        return fun(0,len(preorder)-1, 0, len(inorder)-1)