101.Symmetric Tree
Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).
Example 1:
1
2
| Input: root = [1,2,2,3,4,4,3]
Output: true
|
Example 2:
1
2
| Input: root = [1,2,2,null,3,null,3]
Output: false
|
迭代法：
时间复杂度：O(n)
空间复杂度：O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| bool check(TreeNode *u, TreeNode *v) {
queue <TreeNode*> q;
q.push(u); q.push(v);
while (!q.empty()) {
u = q.front(); q.pop();
v = q.front(); q.pop();
if (!u && !v) continue;
if ((!u || !v) || (u->val != v->val)) return false;
q.push(u->left);
q.push(v->right);
q.push(u->right);
q.push(v->left);
}
return true;
}
bool isSymmetric(TreeNode* root) {
return check(root, root);
}
|
递归法：
时间复杂度：O(n)
空间复杂度：O(n)
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution {
public:
bool check(TreeNode *p, TreeNode *q) {
if (!p && !q) return true;
if (!p || !q) return false;
return p->val == q->val && check(p->left, q->right) && check(p->right, q->left);
}
bool isSymmetric(TreeNode* root) {
return check(root, root);
}
};
|