哪个网站有手机,运营最好的网站,怎么做网络推广挣钱,做网站大流量有序链表转换二叉搜索树
https://leetcode.cn/problems/convert-sorted-list-to-binary-search-tree/description/
描述
给定一个单链表的头节点 head #xff0c;其中的元素 按升序排序 #xff0c;将其转换为 平衡 二叉搜索树
示例 1 输入: head [-10,-3,0,5,9]
输出:…有序链表转换二叉搜索树
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 * 1 0 4 10^4 104] 范围内- 1 0 5 10^5 105 Node.val 1 0 5 10^5 105
Typescript 版算法实现 1 方案1分治
/*** Definition for singly-linked list.* class ListNode {* val: number* next: ListNode | null* constructor(val?: number, next?: ListNode | null) {* this.val (valundefined ? 0 : val)* this.next (nextundefined ? 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 (valundefined ? 0 : val)* this.left (leftundefined ? null : left)* this.right (rightundefined ? 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 (valundefined ? 0 : val)* this.next (nextundefined ? 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 (valundefined ? 0 : val)* this.left (leftundefined ? null : left)* this.right (rightundefined ? 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 (valundefined ? 0 : val)* this.next (nextundefined ? 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 (valundefined ? 0 : val)* this.left (leftundefined ? null : left)* this.right (rightundefined ? null : right)* }* }*/function sortedListToBST(head: ListNode | null): TreeNode | null {const travese (head,tail) {if(headtail) 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)
};
