配置网站开发,有没有专门做家乡图片的网站,wordpress竖版图片尺寸,做网站哪个编辑器好用力扣日记#xff1a;【二叉树篇】108. 将有序数组转换为二叉搜索树 日期#xff1a;2023.1.14 参考#xff1a;代码随想录、力扣 108. 将有序数组转换为二叉搜索树
题目描述 难度#xff1a;简单 给你一个整数数组 nums #xff0c;其中元素已经按 升序 排列#xff0c;…力扣日记【二叉树篇】108. 将有序数组转换为二叉搜索树 日期2023.1.14 参考代码随想录、力扣 108. 将有序数组转换为二叉搜索树
题目描述 难度简单 给你一个整数数组 nums 其中元素已经按 升序 排列请你将其转换为一棵 高度平衡 二叉搜索树。
高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。
示例 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 10^4-10^4 nums[i] 10^4nums 按 严格递增 顺序排列
题解
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
#define SOLUTION 2
public:
#if SOLUTION 1TreeNode* sortedArrayToBST(vectorint nums) {if (nums.size() 0) return nullptr;// 中节点的位置int index nums.size() / 2;TreeNode* node new TreeNode(nums[index]);// 中节点左边和右边的数组分别作为左右子树去构建(左子树为BST 右子树为BST - root为BST)// 而且最后一定也是高度平衡二叉树vectorint leftNum(nums.begin(), nums.begin() index); // 左子树[startIdx, endIdx)vectorint rightNum(nums.begin() index 1, nums.end()); // 右子树node-left sortedArrayToBST(leftNum); // 左子树(自身也是BST)作为左节点node-right sortedArrayToBST(rightNum); // 右子树(自身也是BST)作为右节点return node;}
#elif SOLUTION 2 // 下标索引TreeNode* sortedArrayToBST(vectorint nums) { return buildTree(nums, 0, nums.size() - 1); // 左闭右闭}// 循环不变量左闭右闭 [left, right]// 返回值为构造的二叉树的根节点输入为原始数组以及子数组的起始位置TreeNode* buildTree(vectorint nums, int left, int right) {// 终止条件if (left - right 0) return nullptr; // 相等也是符合条件的,则index left// 获得子数组的中点位置// int index (left right) / 2; // 可能溢出int index left (right - left) / 2;TreeNode* node new TreeNode(nums[index]);// 递归左区间node-left buildTree(nums, left, index - 1); // 左闭右闭// 递归右区间node-right buildTree(nums, index 1, right); // 左闭右闭return node;}
#endif
};复杂度
时间复杂度 空间复杂度
思路总结
构造二叉树本质就是寻找分割点分割点作为当前节点然后递归左区间和右区间。对于二叉搜索树的有序数组其数组中点即为分割点注意在构造二叉树的时候尽量不要重新定义左右区间数组而是用下标来操作原数组解法一和解法二。按照这种方法构造出二叉搜索树自然而然就是高度平衡二叉树
