-
Notifications
You must be signed in to change notification settings - Fork 0
/
SymmetricTree.cpp
64 lines (60 loc) · 1.86 KB
/
SymmetricTree.cpp
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
#include <iostream>
#include <queue>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
/* Analysis
* The key point of this problem is that two nodes (① is left child and ② is right child) in symmetric positions
* must have the same value and the left child of ① should be compared to the right child of ② and
* the right child of ① should be compared to the left child of ②.
*/
/* Sol 0
* Compare recursively.
* Easy to pass.
*/
bool isSymmetric(TreeNode* root) {
if(root==NULL)
return true;
else return isSymmetric(root->left,root->right);
}
bool isSymmetric(TreeNode *left,TreeNode *right){
if(left == NULL && right == NULL)
return true;
if(left == NULL or right == NULL)
return false;
return (left->val == right->val) && isSymmetric(left->left,right->right) && isSymmetric(left->right,right->left);
}
/* Sol 1
* Compare iteratively using queue.
*/
bool isSymmetric2(TreeNode *root){
queue<TreeNode*> p,q;
if(root == NULL)
return true;
p.push(root->left);
q.push(root->right);
while(!p.empty() && !q.empty()){
TreeNode *left = p.front();
TreeNode *right = q.front();
p.pop();
q.pop();
if(left == NULL && right == NULL)
continue;
else if(left == NULL or right == NULL)
return false;
else{
if(left->val != right->val)
return false;
p.push(left->left);p.push(left->right);
q.push(right->right);q.push(right->left);
}
}
return true;
}
};