All files / leetCode 0109.ts

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
 
 
 
 
8x
8x
 
8x
5x
5x
5x
 
 
8x
 
 
 
19x
11x
8x
8x
8x
8x
8x
 
 
 
 
 
4x
1x
3x
 
 
import type { ListNode } from './List'
import { TreeNode } from './Tree'
 
function getMiddle(left: ListNode<number>, right: ListNode<number> | null): ListNode<number> {
  let slow = left
  let fast = left
 
  while (fast !== right && fast.next !== right) {
    slow = slow.next as ListNode<number>
    fast = fast.next as ListNode<number>
    fast = fast.next as ListNode<number>
  }
 
  return slow
}
 
function listToBST(left: ListNode<number>, right: ListNode<number> | null): TreeNode<number> | null {
  if (left === right)
    return null
  const middle = getMiddle(left, right)
  const node = new TreeNode(middle.val)
  node.left = listToBST(left, middle)
  node.right = listToBST(middle.next as ListNode<number>, right)
  return node
}
 
export default function sortedListToBST(
  head: ListNode<number> | null,
): TreeNode<number> | null {
  if (head === null)
    return null
  return listToBST(head, null)
}