recursive dfs O(n)
判断对应子树一样即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
class Solution {
public:
bool isSymmetric(TreeNode* root) {
return !root || isMirror(root->left, root->right);
}
bool isMirror(TreeNode *l, TreeNode *r) {
if (!l && !r) return true;
if (!l || !r || l->val != r->val) return false;
return isMirror(l->left, r->right) && isMirror(l->right, r->left);
}
};
|
iterative bfs O(n)
trick是用一个queue放两个root，然后对于一对left和right分别push left的left，right的right，left的right，right的left
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
|
class Solution {
public:
bool isSymmetric(TreeNode* root) {
queue<TreeNode *> q;
q.push(root);
q.push(root);
while (!q.empty()) {
auto l = q.front(); q.pop();
auto r = q.front(); q.pop();
if (!l && !r) continue;
if (!l || !r || l->val != r->val) return false;
q.push(l->left);
q.push(r->right);
q.push(l->right);
q.push(r->left);
}
return true;
}
};
|
follow up 如果left or right pointer can point to any node in tree
必须要一一对应，要不就是自己
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| unordered_map<TreeNode *, TreeNode *> m;
bool isMirror(TreeNode *l, TreeNode *r) {
if (l == r) {
if (!l) return true;
if (m.count(l)) return m[l] == l;
m[l] = l;
return isMirror(l->left, l->right);
} else {
if (!l || !r) return false;
if (!m.count(l) && !m.count(r)) {
m[l] = r;
m[r] = l;
return isMirror(l->left, r->right) && isMirror(l->right, r->left);
}
return m.count(l) && m.count(r) && m[l] == r && m[r] == l;
}
}
bool isSymmetric(TreeNode *root) {
return isMirror(root, root);
}
|