难度：★★★☆☆
类型：二叉树
方法：递归

题目

力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录

返回与给定前序遍历 preorder 相匹配的二叉搜索树（binary search tree）的根结点。

(回想一下，二叉搜索树是二叉树的一种，其每个节点都满足以下规则，对于 node.left 的任何后代，值总 < node.val，而 node.right 的任何后代，值总 > node.val。此外，前序遍历首先显示节点 node 的值，然后遍历 node.left，接着遍历 node.right。）

题目保证，对于给定的测试用例，总能找到满足要求的二叉搜索树。

示例：

输入：[8,5,1,7,10,12]
输出：[8,5,10,1,7,null,12]

提示：

1 <= preorder.length <= 100
1 <= preorder[i] <= 10^8
preorder 中的值互不相同

解答

什么是二叉搜索树？中序遍历是递增序列的树。这道题目翻译一下，就是给出前序遍历和中序遍历，构造二叉树。

复习一下前序和中序，前序是中左右，后序是左中右，这个不要搞混，前序中的第一个元素一定是根节点，通过寻找根节点在中序中的位置，实际上就找到了中序的划分方式，也就是说，哪部分是左子树，哪部分是右子树，在中序遍历中就明确下来了，不仅如此，有了左子树的数目，前序遍历中的划分方式也就明确。因此可以通过递归实现构建。

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    def bstFromPreorder(self, preorder):
        inorder = sorted(preorder)

        def construct(pre, infix):
            if not pre:
                return

            root = TreeNode(pre[0])
            idx = infix.index(pre[0])
            root.left = construct(pre[1:1+idx], infix[:idx])
            root.right = construct(pre[1+idx:], infix[1+idx:])
            return root

        return construct(preorder, inorder)

如有疑问或建议，欢迎评论区留言~

有关更多力扣中等题的python解决方案，请移步力扣中等题解析