首页 > 其他分享 >101. 对称二叉树

101. 对称二叉树

时间:2023-12-13 23:22:06浏览次数:26  
标签:right return TreeNode 二叉树 对称 101 root 节点 left

1.题目介绍

给你一个二叉树的根节点 \(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\)

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

2.题解

2.1 递归

思路

这里的思路是进行递归搜索,p和q分别走左右两个子树。p向左走看当前节点左子树,q就向右走看当前节点右子树,反之同理。
如果当前节点值均相同说明二叉树对称。反之出现不等值,或者某一子树先行结束说明非对称二叉树

代码

class Solution {
public:
    bool check_mirror(TreeNode* p, TreeNode* q){
        if (!p && !q) return true;
        if (!p || !q) return false;
        return p->val == q->val && check_mirror(p->left, q->right) && check_mirror(p->right,q->left);
    }

    bool isSymmetric(TreeNode* root) {
        if (root == nullptr) return true;
        return check_mirror(root,root);
    }
};

2.2迭代

思路

使用队列存储每层节点,由于其先进先出的特性,每次定是先遍历完一层再进入下一层进行搜寻。
存储的时候采用交错存储来对应二叉树镜像,这边存储一节点的左子节点,接下来就存储对应镜像节点的右子节点(保证镜像性)
并进行结束条件和值是否相等的比较。

代码

class Solution {
public:
    bool check_mirror(TreeNode* root){
        queue<TreeNode*> q;
        q.push(root); q.push(root);
        while (!q.empty()){
            TreeNode* left = q.front(); q.pop();
            TreeNode* right = q.front(); q.pop();
            if (!left && !right) continue;
            if (!left || !right || (left->val != right ->val)) return false;
            q.push(left->left);
            q.push(right->right);
            q.push(left->right);
            q.push(right->left);
        }
        return true;
    }

    bool isSymmetric(TreeNode* root) {
        if (root == nullptr) return true;
        return check_mirror(root);
    }
};;

标签:right,return,TreeNode,二叉树,对称,101,root,节点,left
From: https://www.cnblogs.com/trmbh12/p/17900133.html

相关文章

  • 226. 翻转二叉树
    1.题目介绍给你一棵二叉树的根节点\(root\),翻转这棵二叉树,并返回其根节点。示例1:输入:root=[4,2,7,1,3,6,9]输出:[4,7,2,9,6,3,1]示例2:输入:root=[2,1,3]输出:[2,3,1]示例3:输入:root=[]输出:[]提示:树中节点数目范围在\([0,100]\)内\(-100<=Node.val......
  • [转]cryptoJs DES_CBC_Pkcs7 转成 Java(对称加密早期协议"DES"现已不安全,仅用于老项
    原文地址:cryptoJsDES_CBC_Pkcs7转成Java-唯学而知-博客园前端DES加密:importcryptoJsfrom'crypto-js';//DES加密functionencrypt(message,key,iv){//字符串转16进制constkeyHex=cryptoJs.enc.Utf8.parse(key);constivHex=cryptoJs.enc.U......
  • HASH与对称加密详解
    HASH概述Hash,一般翻译做“散列”,也有直接音译为“哈希”的,就是把任意长度的输入通过散列算法变换成固定长度的输出,该输出就是散列值。这种转换是一种压缩映射,也就是,散列值的空间通常远小于输入的空间,不同的输入可能会散列成相同的输出,所以不可能从散列值来确定唯一的输入值。简......
  • C++堆——heap与二叉树和python
    数据结构栈-->stack队列-->queue树-->tree堆-->heap散列-->hash图-->graph图结构一般包括顶点和边邻接矩阵DAG,DirectedAcyclicGraph即「有向无环图」树树(Tree)是一种非线性的数据结构,由n个节点组成,其中每个节点都有零个或多个子节点。......
  • 三重积分@对称性和奇偶性计算法
    文章目录abstract利用奇偶性利用变量的轮换对称性例(奇偶性和对称性和球坐标)方法1方法2小结abstract除了按定义推导的几种坐标系上的一般计算三重积分的方法这里介绍两类特殊情况,及其可以简化计算的方法利用奇偶性若积分域关于坐标面(即)对称,关于有奇偶性,则若=;=若=;=0若......
  • 线索二叉树记录
                                       中序遍历:   BADCE 将树型结构转换为线性结构,每个结点都有直接前驱和直接后继。              ......
  • 力扣101-对称二叉树
    该题难度为【简单】1.尝试自己写,哪怕写个暴力解法也行,没写出来,看官方题解。2.扫了一眼,不太理解,又想了一会“我代码里漏掉的一半在官方思路中是怎么补上的”,再从头看一遍文字解析,“原来是两棵树对比”。这样思路就清晰了,用递归遍历每个节点,比较每次遍历的“根节点”即可。3.......
  • 257. 二叉树的所有路径
    目录题目题解:前序遍历题目给你一个二叉树的根节点root,按任意顺序,返回所有从根节点到叶子节点的路径。题解:前序遍历classSolution:defbinaryTreePaths(self,root:Optional[TreeNode])->List[str]:res=[]self.getPaths(root,'',re......
  • Leetcode刷题day12-二叉树.前中后序遍历
    递归法实现前.中.后序遍历代码随想录(programmercarl.com)解题思路前序遍历:头->左->右中序遍历:左->头->右后序遍历:左->右->头递归法实现流程:1.定义递归函数;2.寻找递归终止条件;3.设计单层递归模块classSolution(): def__init__(self,val=0,left=None,right=None): sel......
  • 世微 AP5101C 兼容vas1086 高压线性降压恒流车灯驱动IC 宽压5-100V LED电源
      产品描述    AP5101C是一款高压线性LED恒流芯片,外围简单、内置功率管,适用于6-100V输入的高精度降压LED恒流驱动芯片。最大电流2.0A。AP5101C可实现内置MOS做2.0A,外置MOS可做3.0A的。AP5101C内置温度保护功能,温度保护点为130度......