推荐
完整《剑指Offer》算法题解析系列请点击 👉 《剑指Offer》全解析 Java 版
题目描述
请实现一个函数，用来判断一棵二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。
/* public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } */
public class Solution {
boolean isSymmetrical(TreeNode pRoot)
{
}
}
参考思路： 递归
- 判断根结点是否为空
- 判断左右子结点是否相同
- 判断左右子结点的孩子结点是否对称相同
也就是:
左结点的左孩子 == 右结点的右孩子；
左结点的右孩子 == 右结点的左孩子。 - 递归判断。
参考实现：
/* public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } */
public class Solution {
boolean isSymmetrical(TreeNode pRoot)
{
//如果这颗树是个空树，那么当然是对称的，直接返回true。
if (pRoot == null){
return true;
}
//不为空树，则将结点的左右子结点传入方法递归判断。
return semmetrical(pRoot.left, pRoot.right);
}
public boolean semmetrical(TreeNode left, TreeNode right) {
//如果左结点为null，直接判断右结点是不是也为null
if (left == null) {
//注意是判断 == ，不是赋值 =
return right == null;
}
//经过上一个判断，能到这一步说明左结点不为null，而如果此时右结点为null，则直接返回 false
if (right == null) {
return false;
}
//如果左右结点都不为空，则判断它们的值是否相同
if (left.val != right.val) {
return false;
}
//如果左右结点的值相同，则递归继续判断结点的子结点是否对称，即左结点的左孩子 == 右结点的右孩子， 左结点的右孩子 == 右结点的左孩子。
return semmetrical(left.left, right.right) && semmetrical(left.right, right.left);
}
}
看完之后，如果还有什么不懂的，可以在评论区留言，会及时回答更新。
这里是猿兄，为你分享程序员的世界。
非常感谢各位大佬们能看到这里，如果觉得文章还不错的话， 求点赞👍 求关注💗 求分享👬求评论📝 这些对猿兄来说真的 非常有用！！！
注： 如果猿兄这篇博客有任何错误和建议，欢迎大家留言，不胜感激！
京公网安备 11010502036488号