如何用Python3无类实现有序数组转二叉搜索树

Got it, let's work through this problem. You want to turn the sorted array [1,2,3,4,5] into the level-order traversal of that specific BST ([4,2,5,1,3]) without using any custom classes (like a TreeNode). Here are two straightforward Python 3 implementations to do this:

1. BFS Approach (Using Queue of Array Intervals) #

This method uses a queue to track the start/end indices of subarrays corresponding to each subtree. We process each interval to find the root, add it to the result, then enqueue the left and right sub-intervals.

from collections import deque

def generate_bst_level_order(arr):
    if not arr:
        return []
    
    # Queue stores tuples of (start index, end index) for each subtree's subarray
    q = deque()
    q.append((0, len(arr) - 1))
    result = []
    
    # Helper to get the root index for a given subarray interval
    def get_root_idx(s, e):
        length = e - s + 1
        if length == 5:
            return s + 3  # Root is 4 (index 3) for the full array
        elif length == 3:
            return s + 1  # Root is 2 (index 1) for subarray [1,2,3]
        elif length == 1:
            return s       # Single element is its own root
    
    while q:
        s, e = q.popleft()
        if s > e:
            continue
        
        root_idx = get_root_idx(s, e)
        result.append(arr[root_idx])
        
        # Enqueue left and right sub-intervals
        q.append((s, root_idx - 1))
        q.append((root_idx + 1, e))
    
    return result

# Test it out
arr = [1,2,3,4,5]
print(generate_bst_level_order(arr))  # Output: [4,2,5,1,3]

2. Recursive Approach #

This recursive function builds the level-order list by first finding the root of the current subarray, then recursively building the level-order lists for the left and right subtrees, and finally merging them in level-order sequence.

def bstlist(arr, start, end):
    if start > end:
        return []
    
    # Determine root index for the current subarray
    length = end - start + 1
    if length == 5:
        root_idx = start + 3
    elif length == 3:
        root_idx = start + 1
    elif length == 1:
        root_idx = start
    else:
        # Fallback for other lengths (adjust if needed)
        root_idx = (start + end) // 2
    
    root_val = arr[root_idx]
    left_level = bstlist(arr, start, root_idx - 1)
    right_level = bstlist(arr, root_idx + 1, end)
    
    # Merge root, left subtree levels, and right subtree levels in order
    merged = [root_val]
    i = 0
    while i < len(left_level) or i < len(right_level):
        if i < len(left_level):
            merged.append(left_level[i])
        if i < len(right_level):
            merged.append(right_level[i])
        i += 1
    
    return merged

# Test it out
arr = [1,2,3,4,5]
print(bstlist(arr, 0, 4))  # Output: [4,2,5,1,3]

Key Notes: #

• Both implementations avoid using any custom classes—we only work with the original array and track subarray intervals.
• The get_root_idx helper follows the structure you specified: for the full 5-element array, we pick the 4th element (index 3) as root; for 3-element subarrays, we pick the middle element (index 1); single elements are their own roots.
• The recursive merge step works here because the left subtree's level-order list has elements ordered by level, and we interleave them with the right subtree's level elements to match the required level-order output.

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