【5.10】指针算法-快慢指针将有序链表转二叉搜索树

一、题目

        给定一个单链表，其中的 元素按升序排序 ，将其转换为 高度平衡的二叉搜索树 。

        本题中，一个高度平衡二叉树是指一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1。

示例:

给定的有序链表： [ -10 , -3 , 0 , 5 , 9 ],

一个可能的答案是： [ 0 , -3 , 9 , -10 , null , 5 ],

它可以表示下面这个高度平衡二叉搜索树：

          0

        /    \

     -3      9

     /       /

  -10     5

二、解题思路

        二叉搜索树具有这样的特点：当前节点大于左子树的所有节点，同时小于右子树的所有节点，并且每个节点都具备这个特性。

        题中提到，是按照升序排列的单链表，我们只需找到链表的中间节点，使其成为树的根节点。中间节点前面的部分就是根节点左子树的所有节点，中间节点后面的部分就是根节点右子树的所有节点。然后，使用递归的方式再分别对左右子树进行相同的操作……

        这里以链表 1→2→3→4→5 为例来画个图看一下。

        上面链表的中间节点3就是二叉搜索树的根节点，然后再对左右子节点以同样的方式进行操作。最后我们来看看实现代码。

三、代码实现

#include <iostream>
#include <vector>
#include <queue>// 定义链表节点
struct ListNode {int val;ListNode* next;ListNode(int x) : val(x), next(nullptr) {}
};// 定义树节点
struct TreeNode {int val;TreeNode* left;TreeNode* right;TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};// 将有序链表转换为二叉搜索树
TreeNode* sortedListToBST(ListNode* head) {// 边界条件的判断if (head == nullptr)return nullptr;if (head->next == nullptr)return new TreeNode(head->val);// 通过快慢指针找到链表的中间结点slow，pre就是中间结点slow的前一个结点ListNode* slow = head;ListNode* fast = head;ListNode* pre = nullptr;while (fast != nullptr && fast->next != nullptr) {pre = slow;slow = slow->next;fast = fast->next->next;}// 链表断开为两部分，一部分是node的左子节点，一部分是node的右子节点pre->next = nullptr;// node就是当前节点TreeNode* node = new TreeNode(slow->val);// 从head节点到pre节点是node左子树的节点node->left = sortedListToBST(head);// 从slow.next到链表的末尾是node的右子树的结点node->right = sortedListToBST(slow->next);return node;
}// 打印树的层序遍历结果
void printTreeLevelOrder(TreeNode* root) {if (root == nullptr)return;std::queue<TreeNode*> q;q.push(root);bool first = true;while (!q.empty()) {int size = q.size();for (int i = 0; i < size; ++i) {TreeNode* node = q.front();q.pop();if (!first) {std::cout << ", ";}first = false;if (node != nullptr) {std::cout << node->val;q.push(node->left);q.push(node->right);} else {std::cout << "null";}}}std::cout << std::endl;
}// 创建链表
ListNode* createLinkedList(const std::vector<int>& values) {ListNode* dummy = new ListNode(0);ListNode* current = dummy;for (int val : values) {current->next = new ListNode(val);current = current->next;}return dummy->next;
}int main() {// 输入给定的有序链表：[-10, -3, 0, 5, 9]std::vector<int> values = {-10, -3, 0, 5, 9};ListNode* head = createLinkedList(values);// 将有序链表转换为二叉搜索树TreeNode* root = sortedListToBST(head);// 打印树的层序遍历结果std::cout << "[";printTreeLevelOrder(root);std::cout << "]" << std::endl;return 0;
}