-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathbalanced_binary_tree.cpp
More file actions
166 lines (135 loc) · 3.53 KB
/
Copy pathbalanced_binary_tree.cpp
File metadata and controls
166 lines (135 loc) · 3.53 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
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
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
/*
Balanced Binary Tree
Given a binary tree, determine if it is height-balanced.
For this problem, a height-balanced binary tree is defined as a binary tree
in which the depth of the two subtrees of every node never differ by more than 1.
*/
#include <iostream>
#include <algorithm>
using namespace std;
//Definition for binary tree
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL)
{
}
};
// nlogn
class Solution
{
public:
int getHeight(TreeNode *root)
{
if (root == nullptr)
return 0;
return max(getHeight(root->left), getHeight(root->right)) + 1;
}
bool isBalanced(TreeNode *root)
{
if (root == nullptr)
return true;
int leftHeight = getHeight(root->left);
int rightHeiht = getHeight(root->right);
return abs(leftHeight - rightHeiht) <= 1 && isBalanced(root->left)
&& isBalanced(root->right);
}
};
class Solution2
{
private:
bool isBalanced(TreeNode *t, int &depth)
{
if (!t) {
depth = 0;
return true;
}
int leftDepth = 0, rightDepth = 0;
if (isBalanced(t->left, leftDepth) && isBalanced(t->right, rightDepth)) {
if (abs(leftDepth - rightDepth) <= 1) {
depth = max(leftDepth, rightDepth) + 1;
return true;
}
}
return false;
}
public:
bool isBalanced(TreeNode *root)
{
int depth = 0;
return isBalanced(root, depth);
}
};
// cracking the coding interview
// time complexity: O(n)
// space complexity: O(H), H is the height of tree
class Solution3
{
public:
bool isBalanced(TreeNode *root)
{
return checkHeight(root) != -1;
}
private:
int checkHeight(TreeNode *t)
{
if (!t) return 0;
int leftHeight = checkHeight(t->left);
if (leftHeight == -1) return -1; // early return
int rightHeight = checkHeight(t->right);
if (rightHeight == -1) return -1; // early return
// compare
if (abs(leftHeight - rightHeight) > 1) return -1;
return max(leftHeight, rightHeight) + 1; // return height
}
};
class Solution4
{
public:
bool isBalanced(TreeNode *root)
{
bool tag = true;
checkHeight(root, tag);
return tag;
}
private:
int checkHeight(TreeNode *t, bool &tag)
{
if (!tag) return 0; // end as soon as possible
if (!t) return 0;
int leftHeight = checkHeight(t->left, tag);
int rightHeight = checkHeight(t->right, tag);
// compare
if (abs(leftHeight - rightHeight) > 1) {
tag = false;
return 0;
}
return max(leftHeight, rightHeight) + 1;
}
};
int main(int argc, char *argv[])
{
Solution sol;
Solution2 sol2;
Solution3 sol3;
Solution4 sol4;
TreeNode *root = new TreeNode(3);
root->left = new TreeNode(9);
root->right = new TreeNode(20);
root->right->left = new TreeNode(15);
root->right->right = new TreeNode(7);
TreeNode *root2 = new TreeNode(1);
root2->left = new TreeNode(2);
root2->left->left = new TreeNode(3);
cout << sol.isBalanced(root) << endl;
cout << sol.isBalanced(root2) << endl;
cout << sol2.isBalanced(root) << endl;
cout << sol2.isBalanced(root2) << endl;
cout << sol3.isBalanced(root) << endl;
cout << sol3.isBalanced(root2) << endl;
cout << sol4.isBalanced(root) << endl;
cout << sol4.isBalanced(root2) << endl;
return 0;
}