题目描述
给你一个二叉树的根节点 root , 检查它是否轴对称。
示例 1:
输入:root = [1,2,2,3,4,4,3]
输出:true
示例 2:
输入:root = [1,2,2,null,3,null,3]
输出:false
提示:
树中节点数目在范围 [1, 1000] 内
-100 <= Node.val <= 100
进阶:你可以运用递归和迭代两种方法解决这个问题吗?文章来源:https://www.toymoban.com/news/detail-836625.html
递归解法
class Solution {
public boolean isSymmetric(TreeNode root) {
if (root==null){
return true;
}
return judgeIsSymmetric(root.left,root.right);
}
public boolean judgeIsSymmetric(TreeNode leftChild,TreeNode rightChild){
//这种情况是递归出口,当左右孩子都为空的时候就不需要向下判断了,直接返回true
if (leftChild==null&&rightChild==null){
return true;
}
//下面这三种情况都是不满足的时候,都需要返回false
if(leftChild==null&&rightChild!=null){
return false;
}
if (leftChild!=null&&rightChild==null){
return false;
}
if (leftChild.val!= rightChild.val){
return false;
}
//继续往下递归判断,判断左孩子的左孩子和右孩子的右孩子是否对称,判断左孩子的右孩子和右孩子的左孩子是否对称
return judgeIsSymmetric(leftChild.left,rightChild.right)&&judgeIsSymmetric(leftChild.right,rightChild.left);
}
}
非递归解法
思路在代码中详细注释了文章来源地址https://www.toymoban.com/news/detail-836625.html
class Solution {
public boolean isSymmetric(TreeNode root) {
//使用非递归的方式解决
//利用栈来实现,有种消消乐的感觉,依次把对称的两个元素入栈,如果弹出的两个元素不相同则证明不是对称,相同则继续判断
if (root == null) {
return true;
}
Stack<TreeNode> stack = new Stack<>();
stack.push(root.left);
stack.push(root.right);
while (!stack.isEmpty()) {
TreeNode rightChild = stack.pop();
TreeNode leftChild = stack.pop();
//如果左右孩子中有一个不是null但是另一个是null,则肯定不对称
if ((leftChild == null && rightChild != null)||(leftChild!=null&&rightChild==null)) {
return false;
}
if (leftChild != null && rightChild != null) {
//值不相等也肯定不对称
if (leftChild.val != rightChild.val) {
return false;
}
//其他情况就继续探索
//再把对称的元素依次压入其中
stack.push(leftChild.left);
stack.push(rightChild.right);
stack.push(leftChild.right);
stack.push(rightChild.left);
}
}
//都遍历完了之后则表明对称
return true;
}
}
到了这里,关于力扣101 对称二叉树 Java版本的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!