力扣101 对称二叉树 Java版本

这篇具有很好参考价值的文章主要介绍了力扣101 对称二叉树 Java版本。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。


题目描述

给你一个二叉树的根节点 root , 检查它是否轴对称。

示例 1:
力扣101 对称二叉树 Java版本,LeetCode,leetcode,java,算法

输入:root = [1,2,2,3,4,4,3]
输出:true
示例 2:
力扣101 对称二叉树 Java版本,LeetCode,leetcode,java,算法

输入:root = [1,2,2,null,3,null,3]
输出:false

提示:

树中节点数目在范围 [1, 1000] 内
-100 <= Node.val <= 100

进阶:你可以运用递归和迭代两种方法解决这个问题吗?

递归解法

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模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【Leetcode -101.对称二叉树 -144.二叉树的前序遍历】

    题目:给你一个二叉树的根节点 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 思路 :化为子问题比较左子树和右子树是否对称;结束条

    2024年02月09日
    浏览(47)
  • 【递归】【后续遍历】【迭代】【队列】Leetcode 101 对称二叉树

    ---------------🎈🎈对称二叉树 题目链接🎈🎈------------------- 时间复杂度O(N) 空间复杂度O(N)

    2024年02月19日
    浏览(39)
  • Day15|leetcode层序遍历(10道题)、226.翻转二叉树、101.对称二叉树

    视频链接:讲透二叉树的层序遍历 | 广度优先搜索 | LeetCode:102.二叉树的层序遍历_哔哩哔哩_bilibili 看完视频可以一口气做十道题!(102、107、199、637、429、515、116、117、104、111) 二叉树的层序遍历如图所示: 题目链接:226. 翻转二叉树 - 力扣(LeetCode) 视频链接:听说一位

    2024年02月11日
    浏览(67)
  • 算法训练day15Leetcode102二叉树层序遍历226翻转二叉树101对称二叉树

    https://www.bilibili.com/video/BV1ue4y1Y7Mf/?vd_source=8272bd48fee17396a4a1746c256ab0ae 层序遍历一个二叉树。就是从左到右一层一层的去遍历二叉树。这种遍历的方式和我们之前讲过的都不太一样。 需要借用一个辅助数据结构即队列来实现,队列先进先出,符合一层一层遍历的逻辑,而用栈先

    2024年01月18日
    浏览(53)
  • 代码随想录Day12 二叉树 LeetCode T102二叉树的层序遍历 T226 翻转二叉树 T101 对称二叉树

    本文思路和详细讲解来自于:代码随想录 (programmercarl.com) 题目链接:102. 二叉树的层序遍历 - 力扣(LeetCode) 本题使用队列辅助完成,讲解主要函数CheckOrder:首先判断root是否为空,是就直接返回,然后创建队列,向里加入root元素,计算队列的长度,也就是每一层的元素个数,while循环,si

    2024年02月06日
    浏览(44)
  • C++力扣题目101--对称二叉树

    力扣题目链接(opens new window) 给定一个二叉树,检查它是否是镜像对称的。   首先想清楚,判断对称二叉树要比较的是哪两个节点,要比较的可不是左右节点! 对于二叉树是否对称,要比较的是根节点的左子树与右子树是不是相互翻转的,理解这一点就知道了 其实我们要比较

    2024年01月25日
    浏览(37)
  • 【leetcode热题】对称二叉树

    难度: 简单 通过率: 42.2% 题目链接:力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台 给定一个二叉树,检查它是否是镜像对称的。 例如,二叉树  [1,2,2,3,4,4,3]  是对称的。 但是下面这个  [1,2,2,null,3,null,3]  则不是镜像对称的: 说明: 如果你可以运用递归和迭代两种方法

    2024年02月20日
    浏览(33)
  • 【Leetcode】对称二叉树||递归(击败100%)

    step by step. 题目: 给你一棵二叉树的根节点  root  ,翻转这棵二叉树,并返回其根节点。 示例 1: 示例 2: 示例 3: 代码:

    2024年02月13日
    浏览(37)
  • 【Leetcode】相同的树、对称二叉树、另一颗树的子树

    目录 💡相同的树 题目描述 思路: 代码: 💡对称二叉树 题目描述 思路: 代码: 💡另一棵树的子树 题目描述 思路: 代码: 💡总结   给你两棵二叉树的根节点  p  和  q  ,编写一个函数来检验这两棵树是否相同。 如果两个树在结构上相同,并且节点具有相同的值,则

    2024年02月04日
    浏览(39)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包