109. Convert Sorted List to Binary Search Tree
109. Convert Sorted List to Binary Search Tree
🟠 🔖 树
二叉搜索树
链表
分治
二叉树
🔗 LeetCode
题目
Given the head
of a singly linked list where elements are sorted in ascending order , convert it to a height-balanced binary search tree.
Example 1:
![](https://assets.leetcode.com/uploads/2020/08/17/linked.jpg)
Input: head = [-10,-3,0,5,9]
Output: [0,-3,9,-10,null,5]
Explanation: One possible answer is [0,-3,9,-10,null,5], which represents the shown height balanced BST.
Example 2:
Input: head = []
Output: []
Constraints:
- The number of nodes in
head
is in the range[0, 2 * 10^4]
. -10^5 <= Node.val <= 10^5
题目大意
给定一个单链表的头节点 head
,其中的元素 按升序排序 ,将其转换为高度平衡的二叉搜索树。
本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差不超过 1。
解题思路
可以通过递归的方式实现,使用快慢指针找到链表的中间节点,并以中间节点为根构建左右子树。
找到链表的中间节点: 为了构建平衡二叉搜索树,我们需要找到链表的中间节点作为根节点。可以通过快慢指针的方式,一个指针每次走两步,另一个指针每次走一步,直到快指针到达链表末尾,慢指针即为中间节点。在这个过程中,用一个
prev
指针指向中间节点的前一个节点,方便从中间切断链表。以中间节点为根构建左右子树: 将找到的中间节点作为当前子树的根节点,然后递归地构建左子树和右子树。对于左子树,递归处理链表的前半部分;对于右子树,递归处理链表的后半部分。
递归终止条件: 在递归过程中,当链表为空或只有一个节点时,直接返回对应的树节点。这是递归的终止条件。
返回根节点: 最终返回根节点作为整棵平衡二叉搜索树的根。
代码
/**
* @param {ListNode} head
* @return {TreeNode}
*/
var sortedListToBST = function (head) {
if (!head) return null;
// 使用快慢指针找到链表中间节点
let slow = head;
let fast = head;
let prev = null;
while (fast && fast.next) {
prev = slow;
slow = slow.next;
fast = fast.next.next;
}
// 中间节点作为根节点
let root = new TreeNode(slow.val);
// 递归构建左右子树
if (prev) {
prev.next = null; // 切断链表
root.left = sortedListToBST(head);
}
root.right = sortedListToBST(slow.next);
return root;
};
相关题目
- [108. 将有序数组转换为二叉搜索树](./0108.md)
- [2196. 根据描述创建二叉树](./2196.md)