108：将有序数组转换为二叉搜索树
题目：
将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。题目链接
示例：
给定有序数组: [-10,-3,0,5,9],
一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：
0 / \ -3 9 / / -10 5
解法：
class Solution {
private:
TreeNode* buildTree(vector<int>& nums, int left, int right) {
if (left > right) //left和right的相对大小就可以说明问题
return NULL; //无须left < 0 || left > right || right >= len
int mid = (left + right)>>1;
TreeNode* node = new TreeNode(nums[mid]);
node->left = buildTree(nums, left, mid-1);
node->right = buildTree(nums, mid+1, right);
return node;
}
public:
TreeNode* sortedArrayToBST(vector<int>& nums) {
int len = nums.size();
if (len == 0)
return NULL;
return buildTree(nums, 0, len-1); //root的处理和子区间一样，直接调用
}
};
109. 有序链表转换二叉搜索树
题目：
给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。题目链接
示例：
给定的有序链表： [-10, -3, 0, 5, 9],
一个可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树：
0 / \ -3 9 / / -10 5
本题要点：
1：链表升序
2：高度差不超过1，即需要找出中间节点
解法1： 基于108的实现，可将提升难度的链表结构转化为数组
class Solution {
public:
TreeNode* sortedListToBST(ListNode* head) {
vector<int> vec;
while(head != nullptr){
vec.push_back(head->val);
head = head->next;
}
return buildTree(vec, 0, vec.size());
}
TreeNode* buildTree(vector<int>& v, int begin, int end){
if(begin == end)
return nullptr;
int mid = (begin+end)>>1;
TreeNode * root = new TreeNode(v[mid]);
root->left = buildTree(v, begin, mid);
root->right = buildTree(v, mid+1, end);
return root;
}
};
解法2：快慢指针+前序指针找出中间节点前一节点，截断链表
class Solution {
private:
TreeNode* reverseList(ListNode* head) {
if (NULL == head)
return NULL;
ListNode *slow = head, *fast = head, *pre = head; //快慢指针找中点
while (fast && fast->next) { //pre记录中点前一节点
pre = slow;
slow = slow->next;
fast = fast->next->next;
}
TreeNode* node;
if (pre == slow) { //只有一个节点
node = new TreeNode(slow->val);
node->left = NULL;
node->right = NULL;
} else {
slow = pre->next;
pre->next = NULL; //head是左链表头节点，slow是中点
node = new TreeNode(slow->val);
node->left = reverseList(head);
node->right = reverseList(slow->next);
}
return node;
}
public:
TreeNode* sortedListToBST(ListNode* head) {
return reverseList(head);
}
};
这种实现在处理单独节点时显得比较繁琐，可以在返回条件中单独判断只有一个有效节点情况，因为这种情况无法继续截断链表。优化实现如下程序：
class Solution {
private:
TreeNode* reverseList(ListNode* head) {
if (NULL == head)
return NULL;
if (NULL == head->next) //有一个节点时，无法拆分为两个链表
return new TreeNode(head->val);
ListNode *slow = head, *fast = head, *pre = head; //快慢指针找中点
while (fast && fast->next) { //pre记录中点前一节点
pre = slow;
slow = slow->next;
fast = fast->next->next;
}
pre->next = NULL; //head是左链表头节点，slow是中点
TreeNode* node = new TreeNode(slow->val);
node->left = reverseList(head);
node->right = reverseList(slow->next);
return node;
}
public:
TreeNode* sortedListToBST(ListNode* head) {
return reverseList(head);
}
};
解法3：快慢指针，不截断链表，传链表首尾节点
class Solution {
private:
TreeNode* buildTree(ListNode* head, ListNode* tail){
if(head == tail)
return nullptr;
ListNode *slow = head, *fast = head;
while(fast != tail && fast->next != tail){
slow = slow->next;
fast = fast->next->next;
}
TreeNode *root = new TreeNode(slow->val);
root->left = buildTree(head, slow);
root->right = buildTree(slow->next, tail);
return root;
}
public:
TreeNode* sortedListToBST(ListNode* head) {
return buildTree(head, nullptr);
}
};
这种思路很巧妙的一点是，把之前的（fast && fast->next）即已经潜意识的判断(fast != NULL && fast->next != NULL)，变成(fast != tail && fast->next != tail)。冥冥之中，把很多指针的操作都给简化了。
此外，估计有部分同学会想到反转一半的链表，但是就是通不过测试例，那是因为链表本身是升序的，若反转链表，则反转后的链表就是降序了。升序和降序的子链表一样的构造步骤，肯定是不对的。为了构造对的二叉搜索树，这道题不能涉及反转链表，只能是一段段地构造，断不断链表是一种方法，或者修改数据结构。如果更好的思路，欢迎一起探讨。加油。
