数组到 BST 基本情况

Question

我一直在尝试解决有关二叉搜索树的递归问题，但是我没有运气。有人可以用最简单的形式向我解释一下这段代码（在这个问题中广泛使用）如何将数组转换为 BST：

def helper(left, right):

            # base case

            if left > right:

                return None

整个代码（取自leetcode https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/discuss/900790/Python3-with-explanation-faster-than-100-PreOrder-traversal）

def sortedArrayToBST(self, nums: List[int]) -> TreeNode:

        # statrt with the middle element and for the right ones go tree.right and for the left ones go tree.left

        # would have to traverse once so the time complexity will be O(n).

        def helper(left, right):

            # base case

            if left > right:

                return None

            

            # get the length to the nearest whole number

            length  = (left + right) // 2

            

            # preOrder traversal

            root = TreeNode(nums[length])

            root.left = helper(left , length -1)

            root.right = helper(length+1, right)

            return root

        

        return helper(0 , len(nums) - 1)

对此事的任何帮助都会很棒！谢谢

Answer 1

helper(i,j)用于转换array[i:j+1]为 BST。def helper(left, right):            # base case            if left > right:                return None`这个基本情况很重要，因为如果左索引大于右索引，那么逻辑上就不可能为此创建 BST。此外，如果我们不考虑这种情况并中断递归，算法肯定会陷入无限递归。