108. Convert Sorted Array to Binary Search Tree

python

# 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 sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        if not nums:
            return None
        def dfs(left, right):
            # miss part
            # 缺少 left > right 会无限递归
            if left > right:
                return None
            if left == right:
                return TreeNode(nums[left])
            mid = (left + right) // 2
            return TreeNode(nums[mid], dfs(left, mid-1), dfs(mid+1, right))
        return dfs(0, len(nums)-1)

`left > right`

是有一个潜在的问题：当子区间为空（也就是 left > right）时，dfs 里并没有处理，递归会继续下去，从而引发无限递归或对 nums 的越界访问。

出错示例

对于长度为 2 的数组，比如 nums = [1,2]，第一次调用 dfs(0,1)：

计算 mid = 0
递归构造左子树时就会调用 dfs(0, -1)，此时 left > right
进入 dfs(0, -1) 后既不等于也不大于，只按下面的逻辑算 mid = -1，再去访问 nums[-1]，并持续递归……

这样会导致：

对 nums 的非法索引（nums[-1]）
无限递归直至栈溢出

修复方法

在 dfs 一开始加一个对 空区间 的判断：

python

def dfs(left, right):
    if left > right:
        return None
    # （可选）当 left == right 时，可直接返回叶子节点，但实际上下面的逻辑也能兼容
    if left == right:
        return TreeNode(nums[left])
    mid = (left + right) // 2
    return TreeNode(
        nums[mid],
        dfs(left, mid-1),
        dfs(mid+1, right)
    )

或者更简洁地只用一个基准条件：

python

def dfs(left, right):
    if left > right:
        return None
    mid = (left + right) // 2
    node = TreeNode(nums[mid])
    node.left  = dfs(left,  mid-1)
    node.right = dfs(mid+1, right)
    return node

这样就能正确处理所有区间，避免空子树时的越界和无限递归。

More concise solution

python

class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        # 把 nums[left:right] 转成平衡二叉搜索树
        def dfs(left: int, right: int) -> Optional[TreeNode]:
            if left == right:
                return None
            m = (left + right) // 2
            return TreeNode(nums[m], dfs(left, m), dfs(m + 1, right))
        return dfs(0, len(nums))

作者：灵茶山艾府
链接：https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree/solutions/2927064/ru-men-di-gui-cong-er-cha-shu-kai-shi-py-inu6/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

这种解法是左闭右开的写法