【LeetCode 108】算法：将有序数组转换为二叉搜索树
题目：给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 平衡 二叉搜索树。平衡二叉搜索树（Balanced Binary Search Tree，常简称 BBST 或 AVL 树）的核心特点：
[*]首先是：二叉搜索树
左子树所有节点值 < 根值 < 右子树所有节点值，中序遍历结果为升序。
[*]再满足：高度平衡
对任意节点，左右子树高度差绝对值 ≤ 1，整棵树始终保持近似“满/完全”形态，避免退化成链表。
[*]因此，操作复杂
搜索、插入、删除的最坏时间复杂度都为 O(log n)，而非退化时的 O(n)。
[*]需要动态维护
每次插入或删除后，通过旋转（单旋、双旋）、变色等规则自动调整，常见实现有 AVL 树、红黑树、Treap、伸展树等。
本题的核心思路：
升序数组就是 BST 的中序遍历结果；
每次取 中间元素 作为根节点，再递归左右区间，就能保证整棵树 高度平衡。
复杂度：
时间复杂度：O(n)，每个元素只访问一次
空间复杂度：O(log n)，递归栈深度（平衡树高）
Java 代码实现：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
if(nums == null) return new TreeNode();
return build(nums, 0, nums.length-1);
}
// 设左右指针为区间边界。注意指针的变化写法。
private TreeNode build(int[] n, int l, int r){
// 递归出口:左指针大于右指针
if(l > r){
return null;
}
// 1、找到父节点
int mid = (l+r)/2;
TreeNode root = new TreeNode(n);
// 2、在左区间构建左子树
root.left = build(n, l, mid-1);
// 3、在右区间构建右子树
root.right = build(n, mid+1, r);
// 4、返回父节点
return root;
}
}
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！
页:
[1]