将有序数组转换为二叉搜索树
题目要求
你需要编写一个算法，该算法接受一个已经按照升序排列的整数数组 nums 作为输入。你的任务是利用这个数组中的所有元素来创建一棵高度平衡的二叉搜索树（BST）。
在这个上下文中，一棵高度平衡的二叉搜索树定义为一棵二叉树，它满足以下条件：
- 二叉搜索树的性质：对于树中的任意节点，其左子树中的所有元素都小于该节点，其右子树中的所有元素都大于该节点。
- 高度平衡的性质：树中每个节点的左右子树的高度差的绝对值不超过 1。
你的算法需要确保树是平衡的，以避免最坏情况的性能，即退化成链表的情况。
解题思路
要创建一棵高度平衡的二叉搜索树，最直观的方法是始终将数组的中间元素作为二叉树的根节点，这样可以确保左右子树的元素数量尽可能相等，从而保持树的平衡。
具体步骤如下：
-
找到中间元素：首先，找到数组
nums的中间元素，如果数组有偶数个元素，可以选择中间两个元素的任意一个。这个中间元素将成为当前二叉搜索树的根节点。 -
递归构建子树：然后，将中间元素左侧的数组元素用于构建当前根节点的左子树，将中间元素右侧的数组元素用于构建当前根节点的右子树。这一步骤可以递归地进行：
- 对于左子树，取中间元素左侧的子数组，重复步骤 1 和 2，找到子数组的中间元素，作为左子树的根节点。
- 对于右子树，取中间元素右侧的子数组，重复步骤 1 和 2，找到子数组的中间元素，作为右子树的根节点。
-
递归的终止条件：当子数组为空时，递归结束。这意味着当前节点没有子节点。
通过这种方式，可以确保每次都是平均分配元素到左右子树，从而保持整棵树的平衡。递归的过程会一直持续，直到所有的数组元素都已经被用来创建二叉搜索树的节点为止。
Golang 版本
package main
import (
"fmt"
)
// TreeNode is a structure for tree nodes
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
// sortedArrayToBST takes a sorted array and converts it to a balanced BST
func sortedArrayToBST(nums []int) *TreeNode {
if len(nums) == 0 {
return nil
}
return constructBST(nums, 0, len(nums)-1)
}
// constructBST is a helper function that constructs the BST recursively
func constructBST(nums []int, left int, right int) *TreeNode {
if left > right {
return nil
}
mid := left + (right-left)/2
current := &TreeNode{Val: nums[mid]}
current.Left = constructBST(nums, left, mid-1)
current.Right = constructBST(nums, mid+1, right)
return current
}
// printTree is a helper function to print the tree (in-order traversal)
func printTree(node *TreeNode) {
if node == nil {
return
}
printTree(node.Left)
fmt.Print(node.Val, " ")
printTree(node.Right)
}
func main() {
nums := []int{-10, -3, 0, 5, 9}
bst := sortedArrayToBST(nums)
printTree(bst) // Output should be the sorted array in ascending order
}
这段代码定义了一个TreeNode结构体，用于表示二叉树的节点。sortedArrayToBST函数接受一个升序排列的整数数组，并调用constructBST辅助函数来递归地构建高度平衡的二叉搜索树。printTree函数用于以中序遍历的方式打印出树的节点值，以验证树的结构是否正确。在main函数中，我们创建了一个示例数组，并用它来构建 BST，然后打印出来。
C++版本
#include <iostream>
#include <vector>
using namespace std;
// Definition for a binary tree node.
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
TreeNode* sortedArrayToBST(vector<int>& nums) {
return sortedArrayToBST(nums, 0, nums.size() - 1);
}
private:
TreeNode* sortedArrayToBST(vector<int>& nums, int start, int end) {
if (start > end) {
return nullptr;
}
int mid = start + (end - start) / 2;
TreeNode* node = new TreeNode(nums[mid]);
node->left = sortedArrayToBST(nums, start, mid - 1);
node->right = sortedArrayToBST(nums, mid + 1, end);
return node;
}
};
// Helper function to print the tree in-order
void printInOrder(TreeNode* node) {
if (node == nullptr) return;
printInOrder(node->left);
cout << node->val << " ";
printInOrder(node->right);
}
int main() {
vector<int> nums = {-10, -3, 0, 5, 9};
Solution solution;
TreeNode* bst = solution.sortedArrayToBST(nums);
printInOrder(bst); // Should print the numbers in ascending order
return 0;
}
这段 C++代码定义了一个TreeNode结构体，用于表示二叉树的节点，以及一个Solution类，其中包含了sortedArrayToBST函数。这个函数接受一个升序排列的整数数组，并递归地构建一个高度平衡的二叉搜索树。printInOrder函数用于以中序遍历的方式打印出树的节点值，以验证树的结构是否正确。在main函数中，我们创建了一个示例数组，并用它来构建 BST，然后打印出来。
Python 版本
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def sortedArrayToBST(self, nums):
if not nums:
return None
mid = len(nums) // 2
root = TreeNode(nums[mid])
root.left = self.sortedArrayToBST(nums[:mid])
root.right = self.sortedArrayToBST(nums[mid+1:])
return root
def preOrder(node):
if not node:
return
print(node.val, end=' ')
preOrder(node.left)
preOrder(node.right)
# Example usage:
if __name__ == "__main__":
nums = [-10, -3, 0, 5, 9]
sol = Solution()
root = sol.sortedArrayToBST(nums)
preOrder(root) # Pre-order traversal of the BST
这段 Python 代码定义了一个TreeNode类，用于表示二叉树的节点，以及一个Solution类，其中包含了sortedArrayToBST方法。这个方法接受一个升序排列的整数列表，并递归地构建一个高度平衡的二叉搜索树。preOrder函数用于以前序遍历的方式打印出树的节点值，以验证树的结构是否正确。在主函数中，我们创建了一个示例列表，并用它来构建 BST，然后打印出来。
Java 版本
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
if (nums == null || nums.length == 0) {
return null;
}
return constructBSTRecursive(nums, 0, nums.length - 1);
}
private TreeNode constructBSTRecursive(int[] nums, int left, int right) {
if (left > right) {
return null;
}
int mid = left + (right - left) / 2;
TreeNode node = new TreeNode(nums[mid]);
node.left = constructBSTRecursive(nums, left, mid - 1);
node.right = constructBSTRecursive(nums, mid + 1, right);
return node;
}
}
public class Main {
public static void printInOrder(TreeNode node) {
if (node == null) {
return;
}
printInOrder(node.left);
System.out.print(node.val + " ");
printInOrder(node.right);
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] nums = {-10, -3, 0, 5, 9};
TreeNode bst = solution.sortedArrayToBST(nums);
printInOrder(bst); // Should print the numbers in ascending order
}
}
这段 Java 代码定义了一个TreeNode类，用于表示二叉树的节点，以及一个Solution类，其中包含了sortedArrayToBST方法。这个方法接受一个升序排列的整数数组，并递归地构建一个高度平衡的二叉搜索树。printInOrder方法用于以中序遍历的方式打印出树的节点值，以验证树的结构是否正确。在Main类的main方法中，我们创建了一个示例数组，并用它来构建 BST，然后打印出来。
Rust 版本
// Definition for a binary tree node. #[derive(Debug, PartialEq, Eq)] pub struct TreeNode { pub val: i32, pub left: Option<Rc<RefCell<TreeNode>>>, pub right: Option<Rc<RefCell<TreeNode>>>, } impl TreeNode { #[inline] pub fn new(val: i32) -> Self { TreeNode { val, left: None, right: None, } } } use std::rc::Rc; use std::cell::RefCell; pub struct Solution; impl Solution { pub fn sorted_array_to_bst(nums: Vec<i32>) -> Option<Rc<RefCell<TreeNode>>> { Self::sorted_array_to_bst_helper(&nums[..]) } fn sorted_array_to_bst_helper(nums: &[i32]) -> Option<Rc<RefCell<TreeNode>>> { if nums.is_empty() { return None; } let mid = nums.len() / 2; Some(Rc::new(RefCell::new(TreeNode { val: nums[mid], left: Self::sorted_array_to_bst_helper(&nums[..mid]), right: Self::sorted_array_to_bst_helper(&nums[mid + 1..]), }))) } } fn main() { let nums = vec![-10, -3, 0, 5, 9]; let bst = Solution::sorted_array_to_bst(nums); // If you need to print the tree, you will need to implement a function // that traverses the tree and prints its values. }
这段 Rust 代码定义了一个TreeNode结构体，用于表示二叉树的节点，并使用Rc和RefCell来允许可变共享所有权。Solution结构体包含了sorted_array_to_bst方法，该方法接受一个升序排列的 i32 类型向量，并递归地构建一个高度平衡的二叉搜索树。在main函数中，我们创建了一个示例向量，并用它来构建 BST。由于 Rust 的所有权规则，打印树的函数需要特别处理，因此这里没有提供打印函数的实现。如果需要打印树，你需要实现一个遍历树并打印其值的函数。
总结
上面给出了使用不同编程语言（包括 Golang、C++、Python、Java 和 Rust）实现的解决方案，用于将给定的升序排列的整数数组转换为一棵高度平衡的二叉搜索树（BST）。这些解决方案都采用了递归的方法来构建平衡的 BST，具体步骤如下：
- 找到数组的中间元素作为当前子树的根节点。
- 递归地构建当前根节点的左子树和右子树，左子树由中间元素左侧的子数组构成，右子树由中间元素右侧的子数组构成。
- 递归的终止条件是子数组为空时，返回空节点。
这些解决方案都遵循了相似的思路，但在具体实现上有所差异，例如在处理递归终止条件、数组切片、节点的创建等方面。无论使用哪种语言，都可以通过递归的方式轻松地实现这一算法，从而创建一棵高度平衡的二叉搜索树。