-
Notifications
You must be signed in to change notification settings - Fork 41
/
solution.ts
59 lines (54 loc) · 1.73 KB
/
solution.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
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
/**
* 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 printTree (root: TreeNode | null): string[][] {
if (!root) {
return [];
}
const result:string[][] = [];
const height = getHeight(root);
const N = 2 ** height - 1;
for (let i = 0; i < height; i++) {
result[i] = new Array(N).fill('');
}
result[0][N >> 1] = root.val + '';
height > 1 && levelOrder([N >> 1, ], [root, ], result, 1, (N + 1) >> 2);
return result;
}
function levelOrder (indexs:number[], nodes:TreeNode[], result:string[][], row:number, diff:number) {
const nIndexs:number[] = [];
const nNodes:TreeNode[] = [];
for (let i = 0; i < indexs.length; i++) {
const index = indexs[i];
const node = nodes[i];
if (node.left) {
const lIndex = index - diff;
result[row][lIndex] = node.left.val + '';
nIndexs.push(lIndex);
nNodes.push(node.left);
}
if (node.right) {
const rIndex = index + diff;
result[row][rIndex] = node.right.val + '';
nIndexs.push(rIndex);
nNodes.push(node.right);
}
}
nIndexs.length && levelOrder(nIndexs, nNodes, result, row + 1, diff / 2);
}
function getHeight (root:TreeNode|null):number {
if (!root) {
return 0;
}
return Math.max(getHeight(root.left), getHeight(root.right)) + 1;
}