-
Notifications
You must be signed in to change notification settings - Fork 0
/
MaximumDepthBinaryTree.php
80 lines (64 loc) · 1.85 KB
/
MaximumDepthBinaryTree.php
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
<?php
require_once "TreeNode.php";
require_once "TreeHelper.php";
require_once "helpers.php";
class Solution {
/**
* @param TreeNode $root
* @return Integer
*/
function maxDepth($root) {
if($root === null){
return 0;
}
return $this->iteractiveDFS($root);
}
function DFS($root){
return 1 + max($this->maxDepth($root->left), $this->maxDepth($root->right));
}
function BFS($root){
$levels = 0;
$queue = new SplQueue();
$queue->enqueue($root);
while(!$queue->isEmpty()){
$count = $queue->count();
for ($i = 0; $i < $count; $i++){
$node = $queue->dequeue();
if($node->left){
$queue->enqueue($node->left);
}
if($node->right){
$queue->enqueue($node->right);
}
}
$levels++;
}
return $levels;
}
function iteractiveDFS($root){
$stack = [[$root, 1]];
$result = 1;
while(!empty($stack)){
$last = end($stack);
$node = $last[0];
$depth = $last[1];
array_pop($stack);
if($node){
$result = max($result, $depth);
array_push($stack, [$node->left, $depth + 1]);
array_push($stack, [$node->right, $depth + 1]);
}
}
return $result;
}
}
$solution = new Solution();
$root = [3,9,20,null,null,15,7];
$expectedOutput = 3;
checkResult($solution->maxDepth(arrayToTree($root)) === $expectedOutput, 1);
$root = [1,null,2];
$expectedOutput = 2;
checkResult($solution->maxDepth(arrayToTree($root)) === $expectedOutput, 2);
$root = null;
$expectedOutput = 0;
checkResult($solution->maxDepth(arrayToTree($root)) === $expectedOutput, 3);