題目描述：

給定一個整數數組，它表示BST(即 二叉搜索樹 )的 先序遍歷 ，構造樹并返回其根。

保證 對于給定的測試用例，總是有可能找到具有給定需求的二叉搜索樹。

二叉搜索樹 是一棵二叉樹，其中每個節點， Node.left 的任何后代的值 嚴格小于 Node.val , Node.right 的任何后代的值 嚴格大于 Node.val。

二叉樹的 前序遍歷 首先顯示節點的值，然后遍歷Node.left，最后遍歷Node.right。

示例 1：

輸入：preorder = [8,5,1,7,10,12]
輸出：[8,5,10,1,7,null,12]

示例 2:
輸入: preorder = [1,3]
輸出: [1,null,3]

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

解題思路一：題目大致意思就是給定一個二叉樹的前序遍歷，求對應的二叉搜索樹。一種比較特殊的點是「二叉搜索樹」的中序遍歷的結果是【有序序列】，故而我們可以對「前序遍歷」的結果 【排序】 得到「中序遍歷」的結果。從而依據這棵樹的前序和中序遍歷結果構建該「二叉搜索樹」。

對應的題目是105. 從前序與中序遍歷序列構造二叉樹，感興趣的可以看看。

# 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 bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:inorder = sorted(preorder)def myBST(preorder_left: int, preorder_right: int, inorder_left: int, inorder_right: int):if preorder_left > preorder_right:return None# 前序遍歷中的第一個節點就是根節點preorder_root = preorder_left# 在中序遍歷中定位根節點inorder_root = index[preorder[preorder_root]]# 先把根節點建立出來root = TreeNode(preorder[preorder_root])# 得到左子樹中的節點數目size_left_subtree = inorder_root - inorder_left# 遞歸地構造左子樹，并連接到根節點# 先序遍歷中「從 左邊界+1 開始的 size_left_subtree」個元素就對應了中序遍歷中「從 左邊界 開始到 根節點定位-1」的元素root.left = myBST(preorder_left + 1, preorder_left + size_left_subtree, inorder_left, inorder_root - 1)# 遞歸地構造右子樹，并連接到根節點# 先序遍歷中「從 左邊界+1+左子樹節點數目 開始到 右邊界」的元素就對應了中序遍歷中「從 根節點定位+1 到 右邊界」的元素root.right = myBST(preorder_left + 1 + size_left_subtree, preorder_right, inorder_root + 1, inorder_right)return rootn = len(preorder)index = {element: i for i, element in enumerate(inorder)}return myBST(0, n-1, 0, n-1)

構造哈希表的目的是為了，O(1)時間找到中序遍歷結果中的根節點。
時間復雜度：O(nlogn)排序的結果，構造二叉搜索樹的時間復雜度為 O(n)
空間復雜度：O(n)

解題思路二：二分查找左右子樹的分界線遞歸構建左右子樹。可以找到的規律是前序遍歷結果第一個是根節點，而后面的元素可以分為兩個連續的數組，一個數組所有元素嚴格小于根節點，另一個數組所有元素嚴格大于根節點。困難在于快速找到這兩個數組的分界線，這里用的是二分法。

# 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 bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:def dfs(preorder: List[int], left: int, right: int):if left > right: return Noneroot = TreeNode(preorder[left])if left == right: return rootl, r = left, rightwhile(l < r):mid = int(l + (r - l + 1) / 2)if preorder[mid] < preorder[left]: l = mid # 轉到區間[mid, r]else : r = mid -1 # 轉到區間[l, mid -1]# 其實最后l=r是最終的分界線root.left = dfs(preorder, left + 1, l)root.right = dfs(preorder, l + 1, right)return rootn = len(preorder)if n==0: return nullreturn dfs(preorder, 0, n-1)

時間復雜度：O(nlogn)，在找左右子樹分界線的時候時間復雜度為O(logn)；
空間復雜度：O(n)

解題思路三：根據數值上下界遞歸構建左右子樹，我們使用遞歸的方法，在掃描先序遍歷的同時構造出二叉樹。我們在遞歸時維護一個 (lower, upper) 二元組，表示當前位置可以插入的節點的值的上下界。如果此時先序遍歷位置的值處于上下界中，就將這個值作為新的節點插入到當前位置，并遞歸地處理當前位置的左右孩子的兩個位置。否則回溯到當前位置的父節點。

# 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 bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:n = len(preorder)index = 0def dfs(lowerBound: int, upperBound: int):nonlocal index  # 將index聲明為非局部變量if index == n: return Nonecur = preorder[index]if cur < lowerBound or cur > upperBound: return Noneindex += 1root = TreeNode(cur)root.left = dfs(lowerBound, cur)root.right = dfs(cur, upperBound)return rootif n==0: return nullreturn dfs(float('-inf'), float('inf'))

時間復雜度：O(n)
空間復雜度：O(n)

解題思路四：單調棧，思路是維護一個棧頂小棧頂大的單調棧，遍歷一遍前序遍歷結果。如果當前元素大于棧頂元素，則循環出棧找到其父節點node。如果父節點的元素值小于子節點的元素值，則子節點為右孩子，否則為左孩子。代碼邏輯其實很簡單。

# 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 bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:n = len(preorder)if n==0: return nullroot = TreeNode(preorder[0])stack= [root]for i in range(1,n,1):node = stack[-1]currentNode = TreeNode(preorder[i])while stack and stack[-1].val < currentNode.val: node = stack.pop()if node.val < currentNode.val: node.right = currentNodeelse : node.left = currentNodestack.append(currentNode)return root

時間復雜度：O(n)僅掃描前序遍歷一次。
空間復雜度：O(n)用來存儲棧和二叉樹。