1 题目
给定一个单链表，其中的元素按升序排序，请将它转化成平衡二叉搜索树（BST）
2 解法
2.1 转化有序链表为数组
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
class Solution {
public:
/**
*
* @param head ListNode类
* @return TreeNode类
*/
TreeNode* sortedListToBST(ListNode* head) {
// write code here
if (!head)
return nullptr;
vector<int> tmpList;
for (auto p = head; p; p = p->next) {
tmpList.push_back(p->val);
}
TreeNode* res = toBST(0, tmpList.size(), tmpList);
return res;
}
TreeNode* toBST(int start, int end, vector<int> list) {
if (start >= end)
return nullptr;
int target_index = (start + end) / 2;
TreeNode* tmp_res = new TreeNode(list[target_index]);
tmp_res->left = toBST(start, target_index, list);
tmp_res->right = toBST(target_index + 1, end, list);
return tmp_res;
}
};
这么玩儿有点违背出题者初衷了
2.2 用快慢针找到链表中点
