#P4058. 将有序数组转换为二叉搜索树
-
ID: 2300
Tried: 127
Accepted: 25
Difficulty: 3
将有序数组转换为二叉搜索树
题目内容
给你一个整数数组 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<=104
- −104<=nums[i]<=104
- nums按严格递增 顺序排列
将有序数组转换为平衡二叉搜索树
题目描述
给定一个严格递增的整数数组 nums，要求将其转换为 高度平衡 的 二叉搜索树（BST）。
一个高度平衡的二叉搜索树是指一个二叉树中 每个节点的左右子树高度差不超过 1。
题解思路与方法
1. 二叉搜索树（BST）的性质
- 二叉搜索树的中序遍历结果是 有序数组。
- 要构造 高度平衡的 BST，应当尽量 选择数组的中间元素作为根节点，这样左右子树的规模会尽量相等。
2. 递归构造 BST（分治法）
采用 递归+分治 方法，思路如下：
- 取数组
nums[left:right]的 中间元素mid作为根节点。 - 递归构造 左子树，区间为
nums[left:mid-1]。 - 递归构造 右子树，区间为
nums[mid+1:right]。 - 递归终止条件：如果
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;
}