108. 将有序数组转换为二叉搜索树
一句话套路取中点做根,左右两半递归
题目描述
给你一个整数数组 nums ,其中元素已经按 升序 排列,请你将其转换为一棵 平衡 二叉搜索树。
示例 1:
输入:nums = [-10,-3,0,5,9] 输出:[0,-3,9,-10,null,5] 解释:[0,-10,5,null,-3,null,9] 也将被视为正确答案:![]()
示例 2:
输入:nums = [1,3] 输出:[3,1] 解释:[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。
提示:
1 <= nums.length <= 104-104 <= nums[i] <= 104nums按 严格递增 顺序排列
思路
时间
O(n)空间
O(log n)思路
取中间元素做根,左右两半递归建子树 —— 天然高度平衡(AVL 式建法)。
说明
答案不唯一(偶数长度时选中位数左/右都可以),所以测试断言的是「性质」而不是「形状」:中序遍历等于原数组 + 判定为合法 BST。
为了这个断言,本题的 TEST 写到了 Q98 后面(需要复用它的 isValidBST)。
图解
有序数组
[-10,-3,0,5,9]:取中点为根(0),左半[-10,-3]做左子树、右半[5,9]做右子树。因为有序,中点即「大小居中」。逐帧动画
1 / 3
快捷键:← → 单步,空格播放 / 暂停。
C++17 题解
namespace lc0108 {
class Solution {
public:
TreeNode* sortedArrayToBST(vector<int>& nums) { return build(nums, 0, (int)nums.size() - 1); }
private:
static TreeNode* build(const vector<int>& a, int l, int r) {
if (l > r) return nullptr;
int mid = l + (r - l) / 2; // 防溢出写法,面试常问
TreeNode* root = new TreeNode(a[mid]);
root->left = build(a, l, mid - 1);
root->right = build(a, mid + 1, r);
return root;
}
};
}