将有序数组转换为平衡二叉搜索树

题目描述

给定一个严格递增的整数数组 nums，要求将其转换为 高度平衡 的 二叉搜索树（BST）。
一个高度平衡的二叉搜索树是指一个二叉树中 每个节点的左右子树高度差不超过 1。

题解思路与方法

1. 二叉搜索树（BST）的性质

• 二叉搜索树的中序遍历结果是 有序数组。
• 要构造 高度平衡的 BST，应当尽量 选择数组的中间元素作为根节点，这样左右子树的规模会尽量相等。

2. 递归构造 BST（分治法）

采用 递归+分治 方法，思路如下：

1. 取数组 nums[left:right] 的 中间元素 mid 作为根节点。
2. 递归构造 左子树，区间为 nums[left:mid-1]。
3. 递归构造 右子树，区间为 nums[mid+1:right]。
4. 递归终止条件：如果 left > right，返回 None。

3. 层序遍历输出（BFS）

构造完成后，采用 层序遍历（BFS） 输出二叉树，使用 null 代表空节点，去除末尾冗余的 null。

复杂度分析

• 构造 BST：递归地对数组进行二分，每个元素访问一次，时间复杂度为 O(n)。
• 层序遍历：使用队列遍历所有节点，时间复杂度 O(n)。
• 空间复杂度：
  • 递归深度最大为 O(log n)（递归栈）。
  • 额外存储结果数组，空间复杂度为 O(n)。

代码实现

Python 代码

from typing import List, Optional
from collections import deque

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]:
        # 使用分治法递归构造平衡二叉搜索树
        def buildBST(left, right):
            if left > right:
                return None
            mid = (left + right) // 2
            root = TreeNode(nums[mid])
            root.left = buildBST(left, mid - 1)
            root.right = buildBST(mid + 1, right)
            return root

        return buildBST(0, len(nums) - 1)

    def levelOrder(self, root: Optional[TreeNode]) -> List[str]:
        # 层序遍历输出 BST 结果，使用 'null' 表示空节点
        if not root:
            return []
        
        result = []
        queue = deque([root])
        
        while queue:
            node = queue.popleft()
            if node:
                result.append(str(node.val))
                queue.append(node.left)
                queue.append(node.right)
            else:
                result.append("null")

        # 去除末尾的 "null"
        while result and result[-1] == "null":
            result.pop()
        
        return result

# 读取输入并输出
if __name__ == "__main__":
    n = int(input())
    nums = list(map(int, input().split()))
    
    solution = Solution()
    root = solution.sortedArrayToBST(nums)
    print(" ".join(solution.levelOrder(root)))

Java 代码

import java.util.*;

public class Main {
    public class Solution {
        // 二叉树节点定义
        class TreeNode {
            int val;
            TreeNode left, right;
            TreeNode(int x) { val = x; }
        }

        // 递归构造平衡二叉搜索树
        public TreeNode sortedArrayToBST(int[] nums) {
            return buildBST(nums, 0, nums.length - 1);
        }

        private TreeNode buildBST(int[] nums, int left, int right) {
            if (left > right) return null;
            int mid = (left + right) / 2;
            TreeNode root = new TreeNode(nums[mid]);
            root.left = buildBST(nums, left, mid - 1);
            root.right = buildBST(nums, mid + 1, right);
            return root;
        }

        // 层序遍历输出 BST，使用 "null" 表示空节点
        public List<String> levelOrder(TreeNode root) {
            List<String> result = new ArrayList<>();
            if (root == null) return result;

            Queue<TreeNode> queue = new LinkedList<>();
            queue.add(root);
            
            while (!queue.isEmpty()) {
                TreeNode node = queue.poll();
                if (node != null) {
                    result.add(String.valueOf(node.val));
                    queue.add(node.left);
                    queue.add(node.right);
                } else {
                    result.add("null");
                }
            }

            // 去除末尾的 "null"
            while (!result.isEmpty() && result.get(result.size() - 1).equals("null")) {
                result.remove(result.size() - 1);
            }

            return result;
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = scanner.nextInt();
        }
        scanner.close();

        Main main = new Main();
        Solution solution = main.new Solution();
        Solution.TreeNode root = solution.sortedArrayToBST(nums);
        
        List<String> output = solution.levelOrder(root);
        System.out.println(String.join(" ", output));
    }
}

C++ 代码

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

class Solution {
public:
    struct TreeNode {
        int val;
        TreeNode* left;
        TreeNode* right;
        TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    };

    // 递归构建平衡二叉搜索树
    TreeNode* sortedArrayToBST(vector<int>& nums, int left, int right) {
        if (left > right) return nullptr;
        int mid = left + (right - left) / 2;
        TreeNode* root = new TreeNode(nums[mid]);
        root->left = sortedArrayToBST(nums, left, mid - 1);
        root->right = sortedArrayToBST(nums, mid + 1, right);
        return root;
    }

    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return sortedArrayToBST(nums, 0, nums.size() - 1);
    }

    // 层序遍历输出 BST，使用 "null" 表示空节点
    vector<string> levelOrder(TreeNode* root) {
        if (!root) return {};
        vector<string> result;
        queue<TreeNode*> q;
        q.push(root);

        while (!q.empty()) {
            TreeNode* node = q.front();
            q.pop();
            if (node) {
                result.push_back(to_string(node->val));
                q.push(node->left);
                q.push(node->right);
            } else {
                result.push_back("null");
            }
        }

        // 去除末尾的 "null"
        while (!result.empty() && result.back() == "null") {
            result.pop_back();
        }

        return result;
    }
};

int main() {
    int n;
    cin >> n;
    vector<int> nums(n);
    for (int i = 0; i < n; i++) cin >> nums[i];

    Solution solution;
    Solution::TreeNode* root = solution.sortedArrayToBST(nums);
    vector<string> output = solution.levelOrder(root);

    for (size_t i = 0; i < output.size(); i++) {
        if (i > 0) cout << " ";
        cout << output[i];
    }
    cout << endl;

    return 0;
}

题目内容

给你一个整数数组 $nums$，其中元素已经按 升序 排列，请你将其转换为一棵 平衡 二叉搜索树。

输入描述

• 第一行输入一个整数 n，表示数组 nums 的长度。
• 第二行输入 n 个整数，表示数组 nums 的元素，按严格递增顺序排列。

输出描述

输入一行，包含 若干整数，表示二叉树的层序数组表示。 （null表示空节点，输出末尾不能有 null）

样例1

输入

5
-10 -3 0 5 9

输出

0 -3 9 -10 null 5

说明

$[0,-10,5,null,-3,null,9]$也将被视为正确答案：

样例2

输入

2
1 3

输出

3 1

说明

$[1,null,3]$ 和 $[3,1]$ 都是高度平衡二叉搜索树。

提示

• $1 <= nums.length <= 10^4$
• $-10^4 <= nums[i] <= 10^4$
• $nums$按严格递增 顺序排列