1008. 前序遍历构造二叉搜索树

Difficulty
Medium
Tags
二叉树
URL
https://leetcode-cn.com/problems/construct-binary-search-tree-from-preorder-traversal/
Star
给定一个整数数组，它表示BST(即 二叉搜索树 )的 先序遍历 ，构造树并返回其根。
保证 对于给定的测试用例，总是有可能找到具有给定需求的二叉搜索树。
二叉搜索树 是一棵二叉树，其中每个节点， Node.left 的任何后代的值 严格小于 Node.val , Node.right 的任何后代的值 严格大于 Node.val。
二叉树的 前序遍历 首先显示节点的值，然后遍历Node.left，最后遍历Node.right。
示例 1：
notion imagenotion image
输入：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 中的值 互不相同

法 1 两边界限制

思路
notion imagenotion image
notion imagenotion image
先序遍历 ，第一个肯定是根节点，然后之后，小于根节点的都在左子树，大于的都在右子树
题解
# 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]:
        if len(preorder) == 0:
            return None
        if len(preorder) == 1:
            return TreeNode(preorder[0])

        curNode = TreeNode(preorder[0])
        left_pre = [num for num in preorder if num < preorder[0]]
        right_pre = [num for num in preorder if num > preorder[0]]

        curNode.left = self.bstFromPreorder(left_pre)
        curNode.right = self.bstFromPreorder(right_pre)

        return curNode
也可以通过传参的方式，限制左右子树的大小。
# 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]:
        return self.helper(preorder, -float("inf"), float("inf"))

    def helper(self, preorder, min_val ,max_val):
        if len(preorder) == 0:
            return None

        if preorder[0] > max_val or preorder[0] < min_val:
            return None

        cur_node = TreeNode(preorder.pop(0))
        cur_node.left = self.helper(preorder, min_val, cur_node.val)
        cur_node.right = self.helper(preorder, cur_node.val, max_val)

        return cur_node