Skip to content

Commit 37d613a

Browse files
liuyuboboboliuyubobobo
committed
0250 new algo added.
1 parent b4ab34e commit 37d613a

File tree

7 files changed

+194
-2
lines changed

7 files changed

+194
-2
lines changed

‎0250-Count-Univalue-Subtrees/cpp-0250/CMakeLists.txt

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -3,5 +3,5 @@ project(cpp_0250)
33

44
set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -std=c++11")
55

6-
set(SOURCE_FILES main2.cpp)
6+
set(SOURCE_FILES main5.cpp)
77
add_executable(cpp_0250 ${SOURCE_FILES})

‎0250-Count-Univalue-Subtrees/cpp-0250/main.cpp

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,10 +1,12 @@
11
/// Source : https://leetcode.com/problems/count-univalue-subtrees/description/
22
/// Author : liuyubobobo
33
/// Time : 2018-06-02
4+
45
#include <iostream>
56

67
using namespace std;
78

9+
810
/// Definition for a binary tree node.
911
struct TreeNode {
1012
int val;

‎0250-Count-Univalue-Subtrees/cpp-0250/main2.cpp

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,10 +1,12 @@
11
/// Source : https://leetcode.com/problems/count-univalue-subtrees/description/
22
/// Author : liuyubobobo
33
/// Time : 2018-06-02
4+
45
#include <iostream>
56

67
using namespace std;
78

9+
810
/// Definition for a binary tree node.
911
struct TreeNode {
1012
int val;

‎0250-Count-Univalue-Subtrees/cpp-0250/main3.cpp

Lines changed: 57 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,57 @@
1+
/// Source : https://leetcode.com/problems/count-univalue-subtrees/description/
2+
/// Author : liuyubobobo
3+
/// Time : 2018-06-02
4+
5+
#include <iostream>
6+
7+
using namespace std;
8+
9+
10+
/// Definition for a binary tree node.
11+
struct TreeNode {
12+
int val;
13+
TreeNode *left;
14+
TreeNode *right;
15+
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
16+
};
17+
18+
/// Recursive
19+
/// Use class variable to store the result
20+
/// Time Complexity: O(n)
21+
/// Space Complexty: O(h)
22+
class Solution {
23+
24+
private:
25+
int result = 0;
26+
27+
public:
28+
int countUnivalSubtrees(TreeNode* root) {
29+
30+
if(root) dfs(root);
31+
return result;
32+
}
33+
34+
private:
35+
bool dfs(TreeNode* node){
36+
37+
bool ok = true;
38+
if(node->left){
39+
bool isLeft = dfs(node->left);
40+
if(!isLeft || node->val != node->left->val) ok = false;
41+
}
42+
43+
if(node->right){
44+
bool isRight = dfs(node->right);
45+
if(!isRight || node->val != node->right->val) ok = false;
46+
}
47+
48+
if(ok) result ++;
49+
return ok;
50+
}
51+
};
52+
53+
54+
int main() {
55+
56+
return 0;
57+
}

‎0250-Count-Univalue-Subtrees/cpp-0250/main4.cpp

Lines changed: 66 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,66 @@
1+
/// Source : https://leetcode.com/problems/count-univalue-subtrees/description/
2+
/// Author : liuyubobobo
3+
/// Time : 2019-03-02
4+
5+
#include <iostream>
6+
7+
using namespace std;
8+
9+
10+
/// Definition for a binary tree node.
11+
struct TreeNode {
12+
int val;
13+
TreeNode *left;
14+
TreeNode *right;
15+
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
16+
};
17+
18+
/// Recursive
19+
/// Treat null as univalue subtree and make the implementation much more concise :-)
20+
///
21+
/// Time Complexity: O(n)
22+
/// Space Complexty: O(h)
23+
class Solution {
24+
25+
private:
26+
int result = 0;
27+
28+
public:
29+
int countUnivalSubtrees(TreeNode* root) {
30+
31+
dfs(root);
32+
return result;
33+
}
34+
35+
private:
36+
bool dfs(TreeNode* node){
37+
38+
if(!node) return true;
39+
40+
bool isLeft = dfs(node->left), isRight = dfs(node->right);
41+
bool ok = isLeft && (!node->left || node->val == node->left->val) &&
42+
isRight && (!node->right || node->val == node->right->val);
43+
44+
if(ok) result ++;
45+
return ok;
46+
}
47+
};
48+
49+
50+
int main() {
51+
52+
// 5
53+
// / \
54+
// 1 5
55+
// / \ \
56+
// 5 5 5
57+
TreeNode *root = new TreeNode(5);
58+
root->left = new TreeNode(1);
59+
root->right = new TreeNode(5);
60+
root->left->left = new TreeNode(5);
61+
root->left->right = new TreeNode(5);
62+
root->right->right = new TreeNode(5);
63+
cout << Solution().countUnivalSubtrees(root) << endl;
64+
65+
return 0;
66+
}

‎0250-Count-Univalue-Subtrees/cpp-0250/main5.cpp

Lines changed: 65 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,65 @@
1+
/// Source : https://leetcode.com/problems/count-univalue-subtrees/description/
2+
/// Author : liuyubobobo
3+
/// Time : 2019-03-03
4+
5+
#include <iostream>
6+
7+
using namespace std;
8+
9+
10+
/// Definition for a binary tree node.
11+
struct TreeNode {
12+
int val;
13+
TreeNode *left;
14+
TreeNode *right;
15+
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
16+
};
17+
18+
/// Recursive
19+
/// Pass parent value to make the implementation even more concise :-)
20+
///
21+
/// Time Complexity: O(n)
22+
/// Space Complexty: O(h)
23+
class Solution {
24+
25+
private:
26+
int result = 0;
27+
28+
public:
29+
int countUnivalSubtrees(TreeNode* root) {
30+
31+
dfs(root, NULL);
32+
return result;
33+
}
34+
35+
private:
36+
bool dfs(TreeNode* node, TreeNode* parent){
37+
38+
if(!node) return true;
39+
40+
bool isLeft = dfs(node->left, node), isRight = dfs(node->right, node);
41+
if(!isLeft || !isRight) return false;
42+
43+
result ++;
44+
return parent && node->val == parent->val;
45+
}
46+
};
47+
48+
49+
int main() {
50+
51+
// 5
52+
// / \
53+
// 1 5
54+
// / \ \
55+
// 5 5 5
56+
TreeNode *root = new TreeNode(5);
57+
root->left = new TreeNode(1);
58+
root->right = new TreeNode(5);
59+
root->left->left = new TreeNode(5);
60+
root->left->right = new TreeNode(5);
61+
root->right->right = new TreeNode(5);
62+
cout << Solution().countUnivalSubtrees(root) << endl;
63+
64+
return 0;
65+
}

‎readme.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -255,7 +255,7 @@ email: [liuyubobobo@gmail.com](mailto:liuyubobobo@gmail.com)
255255
| 245 | [Shortest Word Distance III](https://leetcode.com/problems/shortest-word-distance-iii/) | [无] | [C++](0245-Shortest-Word-Distance-III/cpp-0245/) | | |
256256
| | | | | | |
257257
| 249 | [Group Shifted Strings](https://leetcode.com/problems/group-shifted-strings/description/) | [无] | [C++](0249-Group-Shifted-Strings/cpp-0249/) | | |
258-
| 250 | [Count Univalue Subtrees](https://leetcode.com/problems/count-univalue-subtrees/description/) | [无] | [C++](0250-Count-Univalue-Subtrees/cpp-0250/) | | |
258+
| 250 | [Count Univalue Subtrees](https://leetcode.com/problems/count-univalue-subtrees/description/) | [solution](https://leetcode.com/problems/count-univalue-subtrees/solution/) | [C++](0250-Count-Univalue-Subtrees/cpp-0250/) | | |
259259
| | | | | | |
260260
| 252 | [Meeting Rooms](https://leetcode.com/problems/meeting-rooms/description/) | [solution](https://leetcode.com/problems/meeting-rooms/solution/) | [C++](0252-Meeting-Rooms/cpp-0252/) | | |
261261
| 253 | [Meeting Rooms II](https://leetcode.com/problems/meeting-rooms-ii/description/) | [solution](https://leetcode.com/problems/meeting-rooms-ii/solution/) | [C++](0253-Meeting-Rooms-II/cpp-0253/) | | |

0 commit comments

Comments
 (0)