-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathsame-tree.php
114 lines (95 loc) · 2.77 KB
/
same-tree.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
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
<!DOCTYPE html>
<html>
<body>
<?php
/*
Problem: https://leetcode.com/problems/same-tree/
Lesson learned:
- to improve runtime -> more efficient conditional statements & faster result return
-
*/
$solution = new Solution();
$result;
/**
* Definition for a binary tree node.
* class TreeNode {
* public $val = null;
* public $left = null;
* public $right = null;
* function __construct($val = 0, $left = null, $right = null) {
* $this->val = $val;
* $this->left = $left;
* $this->right = $right;
* }
* }
*/
class Solution {
/**
* @param TreeNode $p
* @param TreeNode $q
* @return Boolean
*
* Runtime 0ms beats 100%, Memory 19.97mb beats 64.29%
*/
function isSameTree($p, $q) {
if(
($p->val !== $q->val) ||
(($p->left === null) && ($q->left !== null)) ||
(($p->left !== null) && ($q->left === null)) ||
(($p->right !== null) && ($q->right === null)) ||
(($p->right === null) && ($q->right !== null)) ||
((($p->left !== null) && ($q->left !== null)) && (($p->left->value !== $q->left->value) || ($p->right->value !== $q->right->value)))
){
return false;
}
$result = true;
if($p->left === null){
$result = true;
}else{
$result = $this->isSameTree($p->left, $q->left);
}
if($result !== false){
if($p->right === null){
$result = true;
}else{
$result = $this->isSameTree($p->right, $q->right);
}
}
return $result;
}
/**
* @param TreeNode $p
* @param TreeNode $q
* @return Boolean
*
* Runtime 12 ms beats 13.69%, Memory 19.98mb beats 64.29%
*/
function isSameTreeInefficient($p, $q) {
if(
($p->val !== $q->val) ||
(($p->left === null) && ($q->left !== null)) ||
(($p->right !== null) && ($q->right === null)) ||
((($p->left !== null) && ($q->left !== null)) && ($p->left->value !== $q->left->value)) ||
((($p->right !== null) && ($q->right !== null)) && ($p->right->value !== $q->right->value))
){
return false;
}
$result = true;
if(($p->left === null) && ($q->left === null)){
$result = true;
}else{
$result = $this->isSameTree($p->left, $q->left);
}
if($result !== false){
if(($p->right === null) && ($q->right === null)){
$result = true;
}else{
$result = $this->isSameTree($p->right, $q->right);
}
}
return $result;
}
}
?>
</body>
</html>