LeetCode 108：有序数组转二叉搜索树代码输出异常求助

Hey there! Let's break down why your code is producing that massive output array instead of the expected structure.

The Root Cause #

Looking at your recursive sortedBST method, there's a small but critical mistake in how you define the range for the left subtree:

node.left = sortedBST(nums, 0, temp - 1); // ❌ Wrong starting index

You're hardcoding 0 as the starting index for every left subtree recursion, instead of using the current low value passed into the method.

Here's why that breaks things:

• Each time you build a left subtree, you're reprocessing the entire array from index 0 to temp-1, not just the segment that should belong to the current node's left child.
• This causes repeated nesting of nodes, as the same elements get turned into new nodes in different parts of the tree. That's exactly why your output has so many duplicate and extra elements.

The Fix #

Change the left subtree recursion to use the current low parameter instead of 0:

class Solution { 
    public TreeNode sortedArrayToBST(int[] nums) { 
        TreeNode root = sortedBST(nums, 0, nums.length-1); 
        return root; 
    } 
    public TreeNode sortedBST(int[]nums, int low, int high){ 
        if(low > high) return null; 
        int temp = (low + high) / 2; 
        TreeNode node = new TreeNode(nums[temp]); 
        node.left = sortedBST(nums, low, temp - 1); // ✅ Correct range
        node.right = sortedBST(nums, temp + 1, high); 
        return node; 
    } 
}

Why This Works #

With this fix:

1. For the root node (using low=0, high=4 for [-10,-3,0,5,9]), we pick 0 as the root.
2. The left subtree uses the range 0 to 1 (elements [-10,-3]), picking -3 as the left child of 0.
3. The left subtree of -3 uses 0 to 0 (element -10), which becomes its left child.
4. The right subtree of 0 uses 2 to 4 (elements [5,9]), picking 9 as the right child, whose left subtree is 5.

This builds the exact balanced BST you expect, resulting in the output [0,-3,9,-10,null,5].

内容的提问来源于stack exchange，提问作者Simona