Press n or j to go to the next uncovered block, b, p or k for the previous block.
| 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 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 | 341x 341x 341x 97x 17x 80x 80x 80x 80x 296x 296x 151x 151x 106x 106x 106x 296x 136x 136x 110x 110x 110x 80x 123x 72x 51x 17x 17x 17x 17x 17x 17x 17x 17x 17x 17x 17x 17x 6x 1x 5x 5x 5x 5x 5x 16x 5x 5x 37x 21x 21x 16x 16x 16x 16x 50x 16x 34x 34x 20x 14x 5x 17x 5x 5x 12x 12x 7x 5x 12x 27x 9x 18x 7x 11x 11x 11x 11x | class TreeNode<T> {
val: T
left: TreeNode<T> | null
right: TreeNode<T> | null
constructor(val: T) {
this.val = val
this.left = null
this.right = null
}
}
/**
* @param nodes Tree node array (include the `null` node)
* @returns Root of binary tree
*/
function arrayToTree<T>(nodes: (T | null)[]): TreeNode<T> | null {
if (nodes.length === 0)
return null
let nextItem = 0
const root = new TreeNode(nodes[nextItem++] as T)
const queue = [root]
while (queue.length > 0) {
const current = queue.shift() as TreeNode<T>
if (nextItem < nodes.length) {
const item = nodes[nextItem++]
if (item !== null) {
const node = new TreeNode(item)
current.left = node
queue.push(node)
}
}
if (nextItem < nodes.length) {
const item = nodes[nextItem++]
if (item !== null) {
const node = new TreeNode(item)
current.right = node
queue.push(node)
}
}
}
return root
}
type Order = 'pre' | 'in' | 'post'
function traversal<T>(root: TreeNode<T> | null, visitor: (node: T) => void, order: Order = 'in'): void {
if (root === null)
return
switch (order) {
case 'pre':
visitor(root.val)
traversal(root.left, visitor, order)
traversal(root.right, visitor, order)
break
case 'in':
traversal(root.left, visitor, order)
visitor(root.val)
traversal(root.right, visitor, order)
break
case 'post':
traversal(root.left, visitor, order)
traversal(root.right, visitor, order)
visitor(root.val)
break
}
}
class SegmentTree<T> {
private readonly data: T[]
private readonly tree: T[]
private readonly fn: (left: T, right: T) => T
private readonly init: T
constructor(data: T[], fn: (left: T, right: T) => T, init: T) {
if (data.length === 0)
throw new Error('Data is empty')
this.data = data
this.fn = fn
this.init = init
this.tree = Array.from<T>({ length: data.length * 4 }).fill(init)
this.build(0, 0, data.length - 1)
}
public get(index: number): T {
return this.tree[this.getIndex(0, 0, this.data.length - 1, index)]
}
public set(index: number, value: T): void {
this.update(index, value)
}
public query(left: number, right: number): T {
return this.queryHelper(0, 0, this.data.length - 1, left, right)
}
private build(treeIndex: number, left: number, right: number): void {
if (left === right) {
this.tree[treeIndex] = this.data[left]
return
}
const mid = left + ((right - left) >> 1)
this.build(treeIndex * 2 + 1, left, mid)
this.build(treeIndex * 2 + 2, mid + 1, right)
this.tree[treeIndex] = this.fn(
this.tree[treeIndex * 2 + 1],
this.tree[treeIndex * 2 + 2],
)
}
private getIndex(
treeIndex: number,
left: number,
right: number,
index: number,
): number {
if (left === right)
return treeIndex
const mid = left + ((right - left) >> 1)
if (index <= mid)
return this.getIndex(treeIndex * 2 + 1, left, mid, index)
else return this.getIndex(treeIndex * 2 + 2, mid + 1, right, index)
}
private update(index: number, value: T): void {
this.updateHelper(0, 0, this.data.length - 1, index, value)
}
private updateHelper(
treeIndex: number,
left: number,
right: number,
index: number,
value: T,
): void {
if (left === right) {
this.tree[treeIndex] = value
return
}
const mid = left + ((right - left) >> 1)
if (index <= mid)
this.updateHelper(treeIndex * 2 + 1, left, mid, index, value)
else this.updateHelper(treeIndex * 2 + 2, mid + 1, right, index, value)
this.tree[treeIndex] = this.fn(
this.tree[treeIndex * 2 + 1],
this.tree[treeIndex * 2 + 2],
)
}
private queryHelper(
treeIndex: number,
left: number,
right: number,
queryLeft: number,
queryRight: number,
): T {
if (queryLeft <= left && right <= queryRight)
return this.tree[treeIndex]
if (queryRight < left || right < queryLeft)
return this.init
const mid = left + ((right - left) >> 1)
const leftResult = this.queryHelper(
treeIndex * 2 + 1,
left,
mid,
queryLeft,
queryRight,
)
const rightResult = this.queryHelper(
treeIndex * 2 + 2,
mid + 1,
right,
queryLeft,
queryRight,
)
return this.fn(leftResult, rightResult)
}
}
export { arrayToTree, SegmentTree, traversal, TreeNode }
|