101.对称二叉树
题目:
1 | 给定一个二叉树,检查它是否是镜像对称的。 |
- 我的思路:
递归:
函数实现的功能是判断二叉树是否对称
一棵二叉树镜像对称的条件是左子树和右子树镜像对称,那么这棵二叉树镜像对称。那么两棵树满足怎样的条件为镜像对称?
- 根节点相同
- 对于每个节点,都与另一棵树对称
两边不对称时结束(仅一侧为空或两侧不为空但不相等),两边均为空时结束
到达一个节点,首先判断根节点是否对称,再判断左右子树是否对称
代码:
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 /**
* 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 isSymmetric(TreeNode* root) {
if(!root) return true;
auto l = root->left;
auto r = root->right;
return isSym(l, r);
}
private:
bool isSym(TreeNode* lc, TreeNode* rc){
if(lc == nullptr && rc == nullptr) return true;
else if(!lc || !rc) return false;
else if(lc->val != rc->val) return false;
else{
if(isSym(lc->left, rc->right)) return isSym(lc->right, rc->left);
else return false;
}
}
};Note: 出错原因是忘记考虑空输入的特殊测试用例,以及少考虑两侧不为空但不相等的情况
迭代:
先贴代码:
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 /**
* 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 isSymmetric(TreeNode* root) {
if(!root) return true;
auto l = root->left;
auto r = root->right;
queue<TreeNode*> q;
q.push(l);
q.push(r);
while(!q.empty()){
l = q.front();
q.pop();
r = q.front();
q.pop();
if(!l ^ !r) return false;
else if(l!=nullptr && r!=nullptr && (l->val != r->val)) return false;
else if(l == nullptr && r == nullptr) continue;
else{
q.push(l->left);
q.push(r->right);
q.push(l->right);
q.push(r->left);
}
}
return true;
}
};
- 思路比较常规,类似BFS,按层序将两棵树的镜像位置节点取出放入队列,排队比较,每次比较一对。
复习:队列适配器queue,其push操作插入队尾,pop弹出队首。