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

数组到 BST 基本情况

Array to BST base case

python

python-3.x

data-structures

binary-search-tree