Repository navigation
Expand file tree
/
Copy pathlc_101.cpp
More file actions
82 lines (73 loc) · 1.29 KB
/
Copy pathlc_101.cpp
File metadata and controls
82 lines (73 loc) · 1.29 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
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool judgeSymmetric(vector<int>& data)
{
int s = 0, e = data.size() - 1;
while(s < e)
{
if( data[s] != data[e])
return false;
++s;
--e;
}
return true;
}
bool isSymmetric(TreeNode* root)
{
if( root == NULL)
return true;
queue<TreeNode*> q;
int level = 1, next = 0;
q.push(root);
vector<int> data;
TreeNode* top;
while( !q.empty())
{
top = q.front();
--level;
q.pop();
if( top )
{
data.push_back(top->val);
q.push(top->left);
q.push(top->right);
next += 2;
}
else
{
data.push_back(-1);
}
if( level == 0)
{
if( !judgeSymmetric(data))
return false;
else
{
level = next;
next = 0;
data.clear();
}
}
}
return true;
}
};
/*
*using recursive one time traverse
*bool dfs(TreeNode *treel, TreeNode *treer){
* if(!(treel&&treer)) return treel==treer;
* if(!(treel->val == treer->val)) return false;
* return dfs(treel->left, treer->right)&&dfs(treel->right, treer->left);
* }
*
*two level traversal: left to right, right to left
*/