题目描述

blablabla

样例

blablabla

算法1

$O(n^2)$

blablabla

时间复杂度分析：blablabla

C++ 代码

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution(object):
    def buildTree(self, preorder, inorder):
        """
        :type preorder: List[int]
        :type inorder: List[int]
        :rtype: TreeNode
        """
        pos = {}
        n = len(preorder)
        for i in range(n):
            pos[inorder[i]] = i
        return self.dfs(preorder, pos, 0, n - 1, 0, n - 1)

    def dfs(self, pre, pos, pl, pr, il, ir):
        if pl > pr:
            return None
        k = pos[pre[pl]] - il
        root = TreeNode(pre[pl])
        root.left = self.dfs(pre, pos, pl + 1, pl + k, il, il + k - 1)
        root.right = self.dfs(pre, pos, pl + k + 1, pr, il + k + 1, ir)
        return root