難度：★★★☆☆
類型：二叉樹
方法：遞歸

題目

力扣鏈接請移步本題傳送門
更多力扣中等題的解決方案請移步力扣中等題目錄

返回與給定前序遍歷 preorder 相匹配的二叉搜索樹（binary search tree）的根結(jié)點。

(回想一下，二叉搜索樹是二叉樹的一種，其每個節(jié)點都滿足以下規(guī)則，對于 node.left 的任何后代，值總 < node.val，而 node.right 的任何后代，值總 > node.val。此外，前序遍歷首先顯示節(jié)點 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 中的值互不相同

解答

什么是二叉搜索樹？中序遍歷是遞增序列的樹。這道題目翻譯一下，就是給出前序遍歷和中序遍歷，構(gòu)造二叉樹。

復(fù)習(xí)一下前序和中序，前序是中左右，后序是左中右，這個不要搞混，前序中的第一個元素一定是根節(jié)點，通過尋找根節(jié)點在中序中的位置，實際上就找到了中序的劃分方式，也就是說，哪部分是左子樹，哪部分是右子樹，在中序遍歷中就明確下來了，不僅如此，有了左子樹的數(shù)目，前序遍歷中的劃分方式也就明確。因此可以通過遞歸實現(xiàn)構(gòu)建。

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)

如有疑問或建議，歡迎評論區(qū)留言~

有關(guān)更多力扣中等題的python解決方案，請移步力扣中等題解析