数据结构与算法之二叉树: LeetCode 109. 有序链表转换二叉搜索树 (Ts版)

有序链表转换二叉搜索树

• https://leetcode.cn/problems/convert-sorted-list-to-binary-search-tree/description/

描述

• 给定一个单链表的头节点 head ，其中的元素 按升序排序 ，将其转换为 平衡 二叉搜索树

示例 1

输入: head = [-10,-3,0,5,9]
输出: [0,-3,9,-10,null,5]
解释: 一个可能的答案是[0，-3,9，-10,null,5]，它表示所示的高度平衡的二叉搜索树

示例 2

输入: head = []
输出: []

提示

• head 中的节点数在[0, 2 * $10^4$] 范围内
• -$10^5$ <= Node.val <= $10^5$

Typescript 版算法实现

1 ）方案1：分治

/*** Definition for singly-linked list.* class ListNode {*     val: number*     next: ListNode | null*     constructor(val?: number, next?: ListNode | null) {*         this.val = (val===undefined ? 0 : val)*         this.next = (next===undefined ? null : next)*     }* }*//*** Definition for a binary tree node.* class TreeNode {*     val: number*     left: TreeNode | null*     right: TreeNode | null*     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {*         this.val = (val===undefined ? 0 : val)*         this.left = (left===undefined ? null : left)*         this.right = (right===undefined ? null : right)*     }* }*/function sortedListToBST(head: ListNode | null): TreeNode | null {return buildTree(head, null);
}function getMedian(left: ListNode | null, right: ListNode | null): ListNode | null {let fast = left;let slow = left;while (fast !== right && fast?.next !== right) {fast = fast.next?.next || null;slow = slow.next || null;}return slow;
}function buildTree(left: ListNode | null, right: ListNode | null): TreeNode | null {if (left === right) return null;const mid = getMedian(left, right);const root = new TreeNode(mid!.val);root.left = buildTree(left, mid);root.right = buildTree(mid?.next || null, right);return root;
}

2 ）方案2：分治 + 中序遍历优化

/*** Definition for singly-linked list.* class ListNode {*     val: number*     next: ListNode | null*     constructor(val?: number, next?: ListNode | null) {*         this.val = (val===undefined ? 0 : val)*         this.next = (next===undefined ? null : next)*     }* }*//*** Definition for a binary tree node.* class TreeNode {*     val: number*     left: TreeNode | null*     right: TreeNode | null*     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {*         this.val = (val===undefined ? 0 : val)*         this.left = (left===undefined ? null : left)*         this.right = (right===undefined ? null : right)*     }* }*/function sortedListToBST(head: ListNode | null): TreeNode | null {function getLength(head: ListNode | null): number {let length = 0;while (head) {length++;head = head.next;}return length;}function buildTree(left: number, right: number): TreeNode | null {if (left > right) return null;const mid = Math.floor((left + right + 1) / 2);const root = new TreeNode();root.left = buildTree(left, mid - 1);// 更新根节点的值并移动head指针到下一个节点if (head !== null) {root.val = head.val;head = head.next;}root.right = buildTree(mid + 1, right);return root;}const length = getLength(head);return buildTree(0, length - 1);
}

3 ) 方案3：快慢指针

/*** Definition for singly-linked list.* class ListNode {*     val: number*     next: ListNode | null*     constructor(val?: number, next?: ListNode | null) {*         this.val = (val===undefined ? 0 : val)*         this.next = (next===undefined ? null : next)*     }* }*//*** Definition for a binary tree node.* class TreeNode {*     val: number*     left: TreeNode | null*     right: TreeNode | null*     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {*         this.val = (val===undefined ? 0 : val)*         this.left = (left===undefined ? null : left)*         this.right = (right===undefined ? null : right)*     }* }*/function sortedListToBST(head: ListNode | null): TreeNode | null {const travese = (head,tail) => {if(head===tail) return nulllet fast = headlet slow = headwhile(fast!==tail && fast.next!==tail){slow = slow.nextfast = fast.next.next}const root = new TreeNode(slow.val)root.left = travese(head,slow)root.right = travese(slow.next,tail)return root}return travese(head, null)
};