- 前言
掌握了本题能够把二叉树的深度优先搜素和广度优先搜素掌握。以及在此之上的各种变形。
- 题目描述
给定一个二叉树，检查它是否是镜像对称的。
例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
1<br /> / \<br /> 2 2<br /> / \ / \<br />3 4 4 3<br /> <br />但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:1<br /> / \<br /> 2 2<br /> \ \<br /> 3 3<br /> <br />进阶：
你可以运用递归和迭代两种方法解决这个问题吗？
对称二叉树图像(来源leetcode, 侵权请联系删除)示例：
 
- 分析: 如果一个树的左子树与右子树镜像对称，那么这个树是对称的。
如果同时满足下面的条件，两个树互为镜像：
1、它们的两个根结点具有相同的值
2、每个树的右子树都与另一个树的左子树镜像对称
解决：
我们可以实现这样一个递归函数，通过「同步移动」两个指针的方法来遍历这棵树，node1 指针和node2指针一开始都指向这棵树的根，随后 node1 右移时，node2 左移，node1左移时,node2右移。每次检查当前node1和 node2节点的值是否相等，如果相等再判断左右子树是否对称。
// DFS: 深度优先遍历, 简洁优雅。
bool dfs_check(TreeNode *node1, TreeNode *node2)
{
if (!node1 && !node2) return true; // 都为nullptr
if (!node1 || !node2) return false; // 有一个不为nullptr, 不对称
return (node1->val == node2->val)
&& dfs_check(node1->left, node2->right)
&& dfs_check(node1->right, node2->left);
}
bool isSymmetric(TreeNode* root)
{
return dfs_check(root, root); // 对比同一棵树左右
}
// BFS: 广度优先遍历 [美妙]
// 采用队列记录每一层遍历到的节点；
// 并以此插入node1->left以及镜像位置node2->right; node1->right以及镜像位置node2->left.
// 逐层遍历并比较连续两个结点是否为镜像对应节点。
bool bfs_check(TreeNode * node1, TreeNode * node2)
{
queue<TreeNode *> Q;
Q.push(node1);
Q.push(node2);
while(!Q.empty())
{
TreeNode * tmp1 = Q.front(); Q.pop();
TreeNode * tmp2 = Q.front(); Q.pop();
if (!tmp1 && !tmp2) continue; // tmp1和tmp2都为空
// tmp1与tmp2一个不为空或tmp1->val != tmp2->val, 不对称。
if ((!tmp1 || !tmp2) || (tmp1->val != tmp2->val))
return false;
// push(insert) the symmetric points
Q.push(tmp1->left);
Q.push(tmp2->right);
Q.push(tmp1->right);
Q.push(tmp2->left);
}
return true;
}
bool isSymmetric(TreeNode* root)
{
return bfs_check(root, root);
}
欢迎交流，批评指正！
若有收获，就点个赞吧
0 人点赞
