forked from hijiangtao/LeetCode-with-JavaScript
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathres.ts
More file actions
68 lines (63 loc) · 2.26 KB
/
res.ts
File metadata and controls
68 lines (63 loc) · 2.26 KB
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
/**
* 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 getTreeLength(root: TreeNode | null): number {
if (!root) {
return 0;
} else {
return 1 + Math.max(getTreeLength(root.left), getTreeLength(root.right));
}
}
/**
* 自上而下递归
*
* 时间复杂度：O(n^2)，其中 n 是二叉树中的节点个数。
* 最坏情况下，二叉树是满二叉树，需要遍历二叉树中的所有节点，时间复杂度是 O(n)。
* 对于节点 p，如果它的高度是 d，则 height(p) 最多会被调用 d 次（即遍历到它的每一个祖先节点时）。对于平均的情况，一棵树的高度 h 满足 O(h)=O(logn)，因为 d≤h，所以总时间复杂度为 O(nlogn)。对于最坏的情况，二叉树形成链式结构，高度为 O(n)，此时总时间复杂度为 O(n^2)。
*
* 空间复杂度：O(n)，其中 n 是二叉树中的节点个数。空间复杂度主要取决于递归调用的层数，递归调用的层数不会超过 n。
* @param root
*/
function isBalanced(root: TreeNode | null): boolean {
if (!root || !root.left && !root.right) {
return true;
} else {
return isBalanced(root.left) && isBalanced(root.right) && Math.abs(getTreeLength(root.left) - getTreeLength(root.right)) <= 1;
}
};
function getBalancedLength(root: TreeNode | null): number {
if (!root) {
return 0;
} else {
const leftLength = getBalancedLength(root.left);
const rightLength = getBalancedLength(root.right);
if (leftLength < 0 || rightLength < 0 || Math.abs(leftLength - rightLength) > 1) {
return -1;
} else {
return Math.max(leftLength, rightLength) + 1;
}
}
}
/**
* 自底向上的递归
*
* 复杂度均为 O(n)
* @param root
*/
function isBalanced2(root: TreeNode | null): boolean {
if (!root || !root.left && !root.right) {
return true;
} else {
return getBalancedLength(root) >= 0;
}
};