二叉树练习题2-对称二叉树
题目:
给定一个二叉树,检查它是否是镜像对称的。
例如,二叉树 [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
解题思路:
这题的解题方法有递归和迭代两种。
1、递归。
如果一个树的左子树与右子树镜像对称,那么这个树是对称的。
因此,该问题转化为,判断两个左右子树是否彼此镜像
也即判断是否满足以下镜像条件:
1、两子树的根节点值相等
2、一子树的右子树与另一子树的左子树镜像对称,一子树的左子树与另一子树的右子树镜像对称
也就产生了递归关系。
代码表述如下:
bool isMirror(TreeNode* t1,TreeNode* t2)
{
if(t1==NULL && t2==NULL) return true;
if(!t1 || !t2) return false;return isMirror(t1->left,t2->right) && isMirror(t1->right,t2->left);
}
bool isSymmetric(TreeNode* root) {
if(root==NULL) return true;
return isMirror(root,root);
}
2、迭代
思路与上面所述相同,但是采用两个队列实现,队列q1存储左树上的节点,q2存储右树上的节点。