对称二叉树
题目描述：给定一个二叉树，检查它是否是镜像对称的。
例如，二叉树
[1,2,2,3,4,4,3] 是对称的。
1
/ \
2 2
/ \
/ \
3 4 4 3
但是下面这个
[1,2,2,null
,3,null
,3] 则不是镜像对称的
:
1
/ \
2 2
\ \
3 3
说明
:
如果你可以运用递归和迭代两种方法解决这个问题，会很加分。
解题思路：刚开始就想到用队列，类似于BFS的过程，然后将每一层的所有元素都插入到vector中，然后在判断是否对称，但是遇到第二个样例，就没法过测试点了，然后想了一个办法，将空结点的值当作0插入，但是这样的话，就会造成队列永远都不会空，这种方法不行。然后借鉴了一下题解，发现方法很好，就是先是根节点两次入队列，只有连续两次从队列中弹出的元素相等时才是对称的，或者队列空了之后也是对称的。然后对于孩子的左右结点入队列的顺序也很讲究，先是左孩子的左孩子，右孩子的有孩子（因为他们俩是对称的，所以连续存入队列，弹出的时候也一定是连续的）
class Solution {
public:
bool isSymmetric(TreeNode
* root
) {
queue
<TreeNode
*>Q
;
TreeNode
*p
;
int cur_size
,l
,r
;
vector
<int>layer
;
Q
.push(root
);
Q
.push(root
);
while(!Q
.empty()){
TreeNode
*a
,*b
;
a
=Q
.front();
Q
.pop();
b
=Q
.front();
Q
.pop();
if(!a
&&!b
)continue;
if(!a
||!b
)return false;
if(a
->val
!=b
->val
)return false;
Q
.push(a
->left
);
Q
.push(b
->right
);
Q
.push(a
->right
);
Q
.push(b
->left
);
}
return true;
}
};
法二：递归 思路：对于递归，理解的不是很深刻，自己用的时候，就会感觉无从下手，需要专门练习。这一题重在递归的结束条件，以及比较的结点，（两个结点是镜像的，比如左孩子的左孩子和右孩子的右孩子）
class Solution {
public:
bool isSymmetric(TreeNode
* root
) {
if(!root
)return true;
return duichen(root
->left
,root
->right
);
}
bool duichen(TreeNode
*left
,TreeNode
*right
){
if(!left
&&!right
)return true;
if(!left
||!right
)return false;
if(left
->val
==right
->val
){
return duichen(left
->left
,right
->right
)&&duichen(left
->right
,right
->left
);
}
return false;
}
};
