数组到 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。此外，如果我们不考虑这种情况并中断递归，算法肯定会陷入无限递归。