Open Tcdian opened 3 years ago
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {ListNode} head
* @return {TreeNode}
*/
var sortedListToBST = function(head) {
const values = getValues(head);
return buildBST(0, values.length - 1);
function getValues(head) {
const result = [];
while(head !== null) {
result.push(head.val);
head = head.next;
}
return result;
}
function buildBST(start, end) {
if (start > end) {
return null;
}
const mid = (start + end) >> 1;
const root = new TreeNode(values[mid]);
root.left = buildBST(start, mid - 1);
root.right = buildBST(mid + 1, end);
return root;
}
};
/**
* 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 values = getValues(head);
return buildBST(0, values.length - 1);
function getValues(head: ListNode | null): number[] {
const result: number[] = [];
while(head !== null) {
result.push(head.val);
head = head.next;
}
return result;
}
function buildBST(start: number, end: number): TreeNode | null {
if (start > end) {
return null;
}
const mid = (start + end) >> 1;
const root = new TreeNode(values[mid]);
root.left = buildBST(start, mid - 1);
root.right = buildBST(mid + 1, end);
return root;
}
};
109. Convert Sorted List to Binary Search Tree
给定一个单链表,其中的元素按升序排序,将其转换为高度平衡的二叉搜索树。
本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过
1
。Example 1
Example 2
Example 3
Example 4
Note
head
is in the range[0, 2 * 10^4]
.-10^5 <= Node.val <= 10^5