jjzjj

( “树” 之 DFS) 101. 对称二叉树 ——【Leetcode每日一题】

期望上岸的鱼 2024-04-25 原文

101. 对称二叉树

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

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

思路：递归

递归结束条件：

  • 都为空指针则返回 true；
  • 只有一个为空或者对应节点值不相等，则返回 false。

递归过程：

  • 判断 A 的右子树与 B 的左子树是否对称；
  • 判断 A 的左子树与 B 的右子树是否对称；
  • 只有都相等时，才返回true。

代码：(Java、C++)

Java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        return dfs(root.left, root.right);
    }
    public boolean dfs(TreeNode l_root, TreeNode r_root){
        if(l_root == null && r_root == null) return true;
        if(l_root == null || r_root == null || l_root.val != r_root.val){
            return false;
        }
        return dfs(l_root.left, r_root.right) && dfs(l_root.right, r_root.left);
    }
}

C++

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        return dfs(root->left, root->right);
    }
    bool dfs(TreeNode* l_root, TreeNode* r_root){
        if(l_root == NULL && r_root == NULL) return true;
        if(l_root == NULL || r_root == NULL || l_root->val != r_root->val){
            return false;
        }
        return dfs(l_root->left, r_root->right) && dfs(l_root->right, r_root->left);
    }
};

运行结果：

复杂度分析：

  • 时间复杂度： O ( n ) O(n) O(n)，n为节点数，这里遍历了整棵树。
  • 空间复杂度： O ( n ) O(n) O(n)，这里的空间复杂度和递归使用的栈空间有关，这里递归层数不超过 n。

题目来源：力扣。

放弃一件事很容易，每天能坚持一件事一定很酷，一起每日一题吧！
关注我 leetCode专栏，每日更新！

注： 如有不足，欢迎指正！

mdashLeetcodespanclasstoken深度优先算法

有关( “树” 之 DFS) 101. 对称二叉树 ——【Leetcode每日一题】的更多相关文章

  1. Python 刷Leetcode题库，顺带学英语单词（31） - 2

    ValidPalindromeGivenastring,determineifitisapalindrome,consideringonlyalphanumericcharactersandignoringcases. [#125]Example:"Aman,aplan,acanal:Panama"isapalindrome."raceacar"isnotapalindrome.Haveyouconsiderthatthestringmightbeempty?Thisisagoodquestiontoaskduringaninterview.Forthepurposeofthisproblem

  2. ruby - 在 Ruby 中实现二叉树 - 2

    我一直在尝试在Ruby中实现BinaryTree类，但我得到了stackleveltoodeep错误，尽管我似乎没有在该特定代码段中使用任何递归:1.classBinaryTree2.includeEnumerable3.4.attr_accessor:value5.6.definitialize(value=nil)7.@value=value8.@left=BinaryTree.new#stackleveltoodeephere9.@right=BinaryTree.new#andhere10.end11.12.defempty?13.(self.value==nil)?true:

  3. IDEA使用LeetCode插件 - 2

    前言我们习惯用idea编写、调试代码，在LeetCode上刷题时，如果能够在IDEA编写代码，并且做好代码管理，是一件事半功倍的事情。对于后续复习题目，做笔记也会非常便利。本文目的在于介绍LeetCodeEditor的使用，以及配置工具类，最终目录结构如下：note：放置笔记src：放置代码leetcode.editor.cn：插件LeetCodeEditor自动生成utils：自定义的工具包，可用于自动化输入测试用例，定义题目需要的类（结构体）out：运行测试时自动生成LeetCodeEditorGitHub：https://github.com/shuzijun/leetcode-edit

  4. 蓝桥杯C/C++VIP试题每日一练之报时助手 - 2

    ?作者主页：静Yu?简介：CSDN全栈优质创作者、华为云享专家、阿里云社区博客专家，前端知识交流社区创建者?社区地址：前端知识交流社区?博主的个人博客：静Yu的个人博客?博主的个人笔记本：前端面试题个人笔记本只记录前端领域的面试题目，项目总结，面试技巧等等。接下来会更新蓝桥杯官方系统基础练习的VIP试题，依然包括解题思路，源代码等等。问题描述：给定当前的时间，请用英文的读法将它读出来。时间用时h和分m表示，在英文的读法中，读一个时间的方法是：　　如果m为0，则将时读出来，然后加上“o’clock”，如3:00读作“threeo’clock”。　　如果m不为0，则将时读出来，然后将分读出来，如5

  5. Python：每日一题之小张的衣服（优先队列、哈夫曼编码） - 2

    题目描述小张买了 n 件白色的衣服，他觉得所有衣服都是一种颜色太单调，希望对这些衣服进行染色，每次染色时，他会将某种颜色的所有衣服寄去染色厂，第 i 件衣服的邮费为 ai​ 元，染色厂会按照小张的要求将其中一部分衣服染成同一种任意的颜色，之后将衣服寄给小张，请问小张要将 n 件衣服染成不同颜色的最小代价是多少？输入描述第一行为一个整数 n ，表示衣服的数量。第二行包括 n 个整数a1​,a2​...an​ 表示第 i 件衣服的邮费为 ai​ 元。（1≤n≤10^5,1≤ai​≤10^9 ）输出描述输出一个整数表示小张所要花费的最小代价。输入输出样例输入551321输出25 思考🤔：题意：意思是

  6. Ruby OpenSSL 非对称加密——使用两个 key 对 - 2

    我想使用两个key对在两个通信系统之间实现具有不可否认性的安全消息传递。我使用以下方法生成并存储了两组key对:sys1_key=OpenSSL::PKey::RSA.generate(2048)sys2_key=OpenSSL::PKey::RSA.generate(2048)这两个key对都将其单独的公钥和私钥保存到文件中:sys1.pub.pemsys1.priv.pemsys2.pub.pemsys2.priv.pem系统1有自己的公钥和私钥以及系统2的公钥。系统2有自己的公钥和私钥以及系统1的公钥。在系统1上，我想获取消息“Helloworld”并使用系统1的私钥和系统2的公

  7. NEUQ-acm 预备队训练Week4—BFS/DFS - 2

    1.深度优先搜索(DFS)深度优先遍历主要思路是从图中一个未访问的顶点V开始，沿着一条路一直走到底，然后从这条路尽头的节点回退到上一个节点，再从另一条路开始走到底…，不断递归重复此过程，直到所有的顶点都遍历完成。例题P1605迷宫题目描述给定一个N×MN\timesMN×M方格的迷宫，迷宫里有TTT处障碍，障碍处不可通过。在迷宫中移动有上下左右四种方式，每次只能移动一个方格。数据保证起点上没有障碍。给定起点坐标和终点坐标，每个方格最多经过一次，问有多少种从起点坐标到终点坐标的方案。输入格式第一行为三个正整数N,M,TN,M,TN,M,T，分别表示迷宫的长宽和障碍总数。第二行为四个正整数SX,S

  8. 常见搜索模板DFS+BFS+二分搜索【算法】 - 2

     本篇讲的是常见的搜索模板，搜索题的解法时比较固定的，只要把模板记熟，加上自己找几道习题练习体会后，相信各位下次遇到这类题一定能拿下！！下面我将已典型的题目为例子介绍几种常见的搜索方式。 1.二分搜索二分搜索代码模板：例题：#includeusingnamespacestd;doublen;constdoubleeps=1e-12;//二分搜索intmain(){ intt; cin>>t; while(t--){ cin>>n; doublel=0,r=100000,res=-1; while(ln)r=mid-0.0001; elseif(mid*mid*mid二分搜索是只能对有

  9. ruby-on-rails - { "error": { "message": "Missing client_id parameter.", "type": "OAuthException", "code": 101 } } - 2

    我正在关注RyanBatesScreenCast#360Facebook身份验证...当我到达点击链接登录facebook的部分时，我得到一个{"error":{"message":"Missingclient_idparameter.","type":"OAuthException","code":101}}我尝试像之前所说的那样重新启动服务器我正在拔头发试图弄清楚这一点我在facebook开发页面上的网站url是正确的我已经按照他的步骤数百次 最佳答案 可能是你没有为FACEBOOK_KEY和FACEBOOK_SECRET设置e

  10. C++---最长上升子序列模型---最大上升子序列和（每日一道算法2023.3.3） - 2

    注意事项：本题为"线性dp—最长上升子序列的长度"的扩展题，所以dp思路这里就不再赘述。题目：比如，对于序列(1,7,3,5,9,4,8)，有它的一些上升子序列，如(1,7),(3,4,8)等。这些子序列中和最大为18，为子序列(1,3,5,9)的和。你的任务，就是对于给定的序列，求出最大上升子序列和。注意，最长的上升子序列的和不一定是最大的，比如序列(100,1,2,3)的最大上升子序列和为100，而最长上升子序列为(1,2,3)。输入格式输入的第一行是序列的长度N。第二行给出序列中的N个整数，这些整数的取值范围都在0到10000(可能重复)。输出格式输出一个整数，表示最大上升子序列和。数据

随机推荐