LeetCode刷题复盘笔记—一文搞懂有序数组/链表转成二叉搜索树 二叉搜索树变平衡
今日主要总结一下,108. 将有序数组转换为二叉搜索树、109. 有序链表转换二叉搜索树、1382. 将二叉搜索树变平衡,三道同一知识点的题,这三道题一起做可以对这个知识点理解巩固的更加清晰透彻!
题目一:108. 将有序数组转换为二叉搜索树
Leetcode题目地址
题目描述:
给你一个整数数组 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 <= 104
-104 <= nums[i] <= 104
nums 按 严格递增 顺序排列
本题重难点
数组构造二叉树,构成平衡树是自然而然的事情,因为大家默认都是从数组中间位置取值作为节点元素,一般不会随机取,所以想构成不平衡的二叉树是自找麻烦。
关键就是寻找分割点,分割点作为当前节点,然后递归左区间和右区间。而如果要分割的数组长度为偶数的时候,中间元素为两个,是取左边元素和取右边元素都可以,这也是题目中强调答案不是唯一的原因。
这里注意,我这里定义的是左闭右闭区间,在不断分割的过程中,也会坚持左闭右闭的区间
一、正确解法
C++代码
class Solution {
public:
TreeNode* traversal(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 = traversal(nums, left, mid - 1);//左闭右闭区间
root->right = traversal(nums, mid + 1, right);
return root;
}
TreeNode* sortedArrayToBST(vector<int>& nums) {
TreeNode* root = traversal(nums, 0, nums.size() - 1);
return root;
}
};
取数组中间元素的位置,不难写成int mid = (left + right) / 2;,这么写其实有一个问题,就是数值越界,例如left和right都是最大int,这么操作就越界了,在二分法 (opens new window)中尤其需要注意!最好写成 int mid = left + ((right - left) / 2);
注意:在调用traversal的时候为什么传入的left和right为什么是0和nums.size() - 1,因为定义的区间为左闭右闭。
题目二:109. 有序链表转换二叉搜索树
Leetcode题目地址
题目描述:
给定一个单链表的头节点 head ,其中的元素 按升序排序 ,将其转换为高度平衡的二叉搜索树。
本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差不超过 1。
示例 1:
输入: head = [-10,-3,0,5,9]
输出: [0,-3,9,-10,null,5]
解释: 一个可能的答案是[0,-3,9,-10,null,5],它表示所示的高度平衡的二叉搜索树。
示例 2:
输入: head = []
输出: []
提示:
head 中的节点数在[0, 2 * 104] 范围内
-105 <= Node.val <= 105
本题重难点
这道题其实就是上一道题的进阶版本,完全可以是用上一题相同的思路来做,找到链表的中间节点,不断向左右递归建树,而找一个链表的中间节点是一个相当经典的问题,即使用快慢指针的方法!
一、解法一
C++代码
class Solution {
public:
ListNode* getMid(ListNode* left, ListNode* right){
ListNode* slow = left;
ListNode* fast = left;
while(fast != right && fast->next != right){
fast = fast->next;
fast = fast->next;
slow = slow->next;
}
return slow;
}
TreeNode* traversal(ListNode* head, ListNode* left, ListNode* right){
if(left == right) return nullptr;
ListNode* mid = getMid(left, right);
TreeNode* root = new TreeNode(mid->val);
root->left = traversal(head, left, mid);//左闭右开方便表示
root->right = traversal(head, mid->next, right);
return root;
}
TreeNode* sortedListToBST(ListNode* head) {
TreeNode* root = traversal(head, head, nullptr);
return root;
}
};
时间复杂度:O(nlogn),其中 n 是链表的长度。
设长度为 nn 的链表构造二叉搜索树的时间为 T(n),递推式为 T(n)=2⋅T(n/2)+O(n),根据主定理,T(n)=O(nlogn)
方法一的时间复杂度的瓶颈在于寻找中位数节点。由于构造出的二叉搜索树的中序遍历结果就是链表本身,因此我们可以将分治和中序遍历结合起来,减少时间复杂度,对方法一进行优化!
二、优化解法
C++代码
class Solution {
public:
int getLength(ListNode* head) {
int count = 0;
for(ListNode* cur = head; cur != nullptr; cur = cur->next){
count++;
}
return count;
}
TreeNode* buildTree(ListNode*& head, int left, int right) {
if(left > right) return nullptr;
int mid = left + (right - left) / 2;
TreeNode* root = new TreeNode();
root->left = buildTree(head, left, mid - 1);
root->val = head->val;
head = head->next;
root->right = buildTree(head, mid + 1, right);
return root;
}
TreeNode* sortedListToBST(ListNode* head) {
int len = getLength(head);
TreeNode* res = buildTree(head, 0, len - 1);
return res;
}
};
这个方法特别巧妙可以好好品味一下!
题目三:1382. 将二叉搜索树变平衡
Leetcode题目地址
题目描述:
给你一棵二叉搜索树,请你返回一棵 平衡后 的二叉搜索树,新生成的树应该与原来的树有着相同的节点值。如果有多种构造方法,请你返回任意一种。
如果一棵二叉搜索树中,每个节点的两棵子树高度差不超过 1 ,我们就称这棵二叉搜索树是 平衡的 。
示例 1:
输入:root = [1,null,2,null,3,null,4,null,null]
输出:[2,1,3,null,null,null,4]
解释:这不是唯一的正确答案,[3,1,4,null,2,null,null] 也是一个可行的构造方案。
示例 2:
输入: root = [2,1,3]
输出: [2,1,3]
提示:
树节点的数目在 [1, 104] 范围内。
1 <= Node.val <= 105
本题重难点
这道题目,可以中序遍历把二叉树转变为有序数组,然后在根据有序数组构造平衡二叉搜索树。所以做这道题之前一定先做一下108.将有序数组转换为二叉搜索树这道题!
一、解法
C++代码
class Solution {
public:
vector<int> vec;
void traversal(TreeNode* node){
if(!node) return;
traversal(node->left);
vec.push_back(node->val);
traversal(node->right);
}
TreeNode* getTree(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 = getTree(nums, left, mid - 1);
root->right = getTree(nums, mid + 1, right);
return root;
}
TreeNode* balanceBST(TreeNode* root) {
traversal(root);
TreeNode* res = getTree(vec, 0, vec.size() - 1);
return res;
}
};
总结
这三道题基本上都是一类题,主要就是关于将有序数据结构转成二叉搜索树,还有将二叉搜索树变平衡的问题!
一定要尽量用号二叉搜索树中序遍历有序的特性,可以更好的解决问题!
欢迎大家关注本人公众号:编程复盘与思考随笔
(关注后可以免费获得本人在csdn发布的资源源码)
公众号主要记录编程和刷题时的总结复盘笔记和心得!并且分享读书、工作、生活中的一些思考感悟!