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:

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。

解题思路

可以通过递归的方式实现，使用快慢指针找到链表的中间节点，并以中间节点为根构建左右子树。

1. 找到链表的中间节点： 为了构建平衡二叉搜索树，我们需要找到链表的中间节点作为根节点。可以通过快慢指针的方式，一个指针每次走两步，另一个指针每次走一步，直到快指针到达链表末尾，慢指针即为中间节点。在这个过程中，用一个 prev 指针指向中间节点的前一个节点，方便从中间切断链表。

2. 以中间节点为根构建左右子树： 将找到的中间节点作为当前子树的根节点，然后递归地构建左子树和右子树。对于左子树，递归处理链表的前半部分；对于右子树，递归处理链表的后半部分。

3. 递归终止条件： 在递归过程中，当链表为空或只有一个节点时，直接返回对应的树节点。这是递归的终止条件。

4. 返回根节点： 最终返回根节点作为整棵平衡二叉搜索树的根。

代码

/**
 * @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. 将有序数组转换为二叉搜索树
• 2196. 根据描述创建二叉树

- [108. 将有序数组转换为二叉搜索树](./0108.md)
- [2196. 根据描述创建二叉树](./2196.md)