101. Symmetric Tree
Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).
Follow up: Could you solve it both recursively and iteratively?
- Iteratively solution
- Time : O(n)
- Space : O(n)
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
|
class Solution {
public:
bool isSymmetric(TreeNode* root) {
queue<TreeNode*> left, right;
left.push(root->left);
right.push(root->right);
while(!left.empty() and !right.empty()) {
auto l = left.front(); left.pop();
auto r = right.front(); right.pop();
if(!l and !r) continue;
if((!l and r) or (!r and l) or (l->val != r->val)) return false;
left.push(l->left); left.push(l->right);
right.push(r->right); right.push(r->left);
}
return left.empty() and right.empty();
}
};
|
- Recursively solution
- Time : O(n)
- Space : O(1) but use call stack O(h)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| /**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
bool solution(TreeNode* l, TreeNode* r) {
if(!l and !r) return true;
if((!l and r) or (!r and l) or (l->val != r->val)) return false;
return solution(l->left, r->right) and solution(l->right, r->left);
}
public:
bool isSymmetric(TreeNode* root) {
return solution(root->left, root->right);
}
};
|
