【LeetCode经典题解】递归破解对称二叉树之谜

🎁个人主页：User_芊芊君子
🎉欢迎大家点赞👍评论📝收藏⭐文章
🔍系列专栏：Java.数据结构

【前言】

在二叉树的各类算法问题中，“判断二叉树是否对称”是经典且基础的题型，它不仅能考查对二叉树结构的理解，更能体现递归思想的灵活运用。对称二叉树的核心特征是：树的左子树与右子树呈现镜像关系，即左子树的左子树和右子树的右子树对称、左子树的右子树和右子树的左子树对称。本文将基于递归的思路，拆解这道题的解题逻辑，帮助读者深入理解二叉树的对称性判断。

文章目录：

• 一、对称二叉树
• 二、思路分析
  • 1. 边界处理
  • 2. 递归比较左右子树
  • 3. 辅助方法isSymmetric2()具体实现逻辑
• 三、代码详解
• 四、总结

一、对称二叉树

二、思路分析

1. 边界处理

先判断跟是否为空，如果为空的话，也可以认为是对称的；

2. 递归比较左右子树

在isSymmetric()方法中，只有一个参数，显然是无法解决下面两个子树的问题，所以再构造一个方法：isSymmetric2()作为辅助方法，传入节点的左右子树，从顶层开始逐层，逐节点比较；

3. 辅助方法isSymmetric2()具体实现逻辑

如果左子树为空，右子树不为空，或者左子树不为空，右子树为空，说明不对称，返回false；如果左子树和右子树都为空，说明也是对称的，返回true；剩下的就是左子树和右子树都不为空的情况，然后判断它们的val值是否相同，如果不相同，说明不对称，返回false；递归比较左子树的左节点和右子树的右节点，左子树的右节点和右子树的左节点是否相同，相同说明对称，返回true.

三、代码详解

publicbooleanisSymmetric(TreeNode root){if(root ==null){returntrue;}returnisSymmetric2(root.left, root.right);}publicbooleanisSymmetric2(TreeNode leftTree,TreeNode rightTree){if((leftTree ==null&& rightTree !=null)||(leftTree !=null&& rightTree ==null)){returnfalse;}if(leftTree ==null&& rightTree ==null){returntrue;}if(leftTree.val != rightTree.val){returnfalse;}returnisSymmetric2(leftTree.left, rightTree.right)&&isSymmetric2(leftTree.right, rightTree.left);}

四、总结

本题通过递归的方式，巧妙地将“二叉树是否对称”的问题拆解为“左右子树是否镜像”的子问题，再进一步拆解为“对应位置子树是否对称”的更小问题，充分体现了递归“分而治之”的思想。