forked from DaleStudy/leetcode-study
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathreeseo3o.js
More file actions
39 lines (31 loc) · 758 Bytes
/
reeseo3o.js
File metadata and controls
39 lines (31 loc) · 758 Bytes
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
/**
* DFS
* Time complexity: O(n)
* Space complexity: O(h) - h is the height of the tree, worst case O(n)
*/
const maxDepth = (root) => {
if (root === null) return 0;
const leftDepth = maxDepth(root.left);
const rightDepth = maxDepth(root.right);
return 1 + Math.max(leftDepth, rightDepth);
};
/**
* BFS
* Time complexity: O(n)
* Space complexity: O(n)
*/
const maxDepthBFS = (root) => {
if (root === null) return 0;
const queue = [root];
let depth = 0;
while (queue.length > 0) {
const levelSize = queue.length;
for (let i = 0; i < levelSize; i++) {
const node = queue.shift();
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
depth++;
}
return depth;
};