101 对称二叉树

01

题目信息

题目地址: https://leetcode-cn.com/problems/symmetric-tree/

给定一个二叉树,检查它是否是镜像对称的。

示例1:是对称的

    1
   / \
  2   2
 / \ / \
3  4 4  3

示例2:不对称

    1
   / \
  2   2
   \   \
   3    3

02

解法一:递归

我们先来划分子问题,一个树对称也就最终根节点的左子树与右子树是对称的镜像的,那么要求左子节点与右子节点相等的同时左节点的左子树(右子树)与右节点的右子树(左子树)对称,还是画个图吧

我们传入这两颗树看是否对称,那么有三个操作:

  • 第一两个根节点是否相等
  • 第二它左子树是否与另外一个的右子树对称
  • 第三它的右子树是否与另外一个的左子树对称

每次递归传递一对树,直到最后叶子只有节点节点比较

public boolean isSymmetric(TreeNode root) {
    //第一次传root让下面顺便进行空判断
    return check(root, root);
}
public boolean check(TreeNode p, TreeNode q) {
    //都为空则没有子树,两个根相等就是对称
    if (p == null && q == null) return true;
    //不满足上面条件,则是一个有子树一个没有那么不对称
    if (p == null || q == null) return false;
    //三个条件结合
    return p.val == q.val && check(p.left, q.right) && check(p.right, q.left);
}

遍历了整颗树时间复杂度为O(n),递归系统栈占用大小取决于树的层度这里不是完全二叉树所以它只是小于n空间复杂度为O(n)

03

方法二:迭代

递归思路写完了,栈换成队列使用广度的方式完成同样的思路,还是再画个图

通过队列依次按照顺序比较offer进队列时就是一个树的左(右)与另一个树的右(左),poll出队列的两个也就是对应的,直到对队列没有后续进来的为空了仍然没出现不满足情况的,则是对称二叉树

public boolean isSymmetric(TreeNode root) {
    return check(root, root);
}

public boolean check(TreeNode p, TreeNode q) {
    Queue<TreeNode> queue = new LinkedList<TreeNode>();
    queue.offer(p);
    queue.offer(q);
    while (!queue.isEmpty()) {
        //每次出两个
        p = queue.poll();
        q = queue.poll();
        //对称比较的条件
        if (p == null && q == null) continue;
        if ((p == null || q == null) || (p.val != q.val)) return false;
        //按顺序进队列
        queue.offer(p.left);
        queue.offer(q.right);

        queue.offer(p.right);
        queue.offer(q.left);
    }
    return true;
}

时间复杂度与空间复杂度同上

04

总结

无外乎深度优先与广度优先,上面的两种解都是优的解在一次树的遍历过程中完成对是否是对称的判断。如果直接暴力的还可先遍历一遍得到序列或者数组再判断,比如先序遍历与后序遍历序列相反,比如中序遍历结果是回文的,总之我们要先对遍历熟悉。

本文分享自微信公众号 - IT那个小笔记(Jasper-zh_blog),作者:木瓜煲鸡脚

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-12-23

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 101. 对称二叉树

    Michel_Rolle
  • 101. 对称二叉树

    杨鹏伟
  • LeetCode-101.对称二叉树

    链接:https://leetcode-cn.com/problems/symmetric-tree/description/ 给定一个二叉树,检查它是否是它自...

    张诺谦
  • 【Leetcode】101. 对称二叉树

    入队顺序依次是, 左子树的左儿子,右子树的右儿子 左子树的右儿子,右子树左右儿子。 这样出队的时候两两检查是不是对称。

    Leetcode名企之路
  • Leetcode 101. 对称二叉树

    以 t1、t2 表示二叉树的左子树和右子树,若 t1 与 t2 对称,则二叉树对称;若 t1 的根节点值与 t2 的根节点值相等,且 t1 的左子树与 t2 的...

    zhipingChen
  • LeetCode 101.对称二叉树 - JavaScript

    心谭博客
  • Leetcode No.101 对称二叉树

    1 / \ 2 2 / \ / \ 3 4 4 3

    week
  • LeetCode 101: 对称二叉树 Symmetric Tree

    Given a binary tree, check whether it is a mirror of itself (ie, symmetric aroun...

    爱写bug
  • ​LeetCode刷题实战101:对称二叉树

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就...

    程序IT圈
  • LeetCode 101. 对称二叉树(递归&循环)

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/symmetric-tree 著作权归领扣网络所有。...

    Michael阿明
  • 天天算法 LeetCode-101-对称二叉树

    https://leetcode-cn.com/problems/symmetric-tree/

    FunTester
  • 天天算法 LeetCode-101-对称二叉树

    https://leetcode-cn.com/problems/symmetric-tree/

    灵魂画师牧码
  • 每天一道leetcode-101对称二叉树

    今天的题目 每天的题目见github(看最新的日期): https://github.com/gzc426 具体的题目可以去牛客网对应专题去找。

    乔戈里
  • Leetcode|二叉树的属性|101. 对称二叉树

    SL_World
  • 对称二叉树

    对称二叉树 【问题描述】     如果二叉树的左右子树的结构是对称的,即两棵子树皆为空,或者皆不空,则称该二叉树是对称的。编程判断给定的二叉树是否对称.    ...

    attack
  • 对称二叉树

    源:力扣(LeetCode)链接:https://leetcode-cn.com/problems/symmetric-tree/submissions/

    double
  • 对称的二叉树

    一份执着✘
  • [剑指offer] 对称的二叉树

    请实现一个函数,用来判断一颗二叉树是不是对称的。注意,如果一个二叉树同此二叉树的镜像是同样的,定义其为对称的。

    尾尾部落
  • [leetcode二叉树系列]4 对称二叉树

    二叉树的遍历和队列的相关概念前面已经介绍,忘记了的小伙伴复习后再看效果一定翻倍哟!

    我是程序员小贱

扫码关注云+社区

领取腾讯云代金券