每日一题——对称的二叉树

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

题目


给定一棵二叉树,判断其是否是自身的镜像(即:是否对称)

例如:
下面这棵二叉树是对称的

每日一题——对称的二叉树,算法,算法

下面这棵二叉树不对称。

每日一题——对称的二叉树,算法,算法

数据范围:节点数满足 0≤n≤1000,节点上的值满足 ∣val∣≤1000

要求:空间复杂度 O(n),时间复杂度 O(n)

参数说明:二叉树类,二叉树序列化是通过按层遍历,#代表这这个节点为空节点,举个例子:

  1
 / \
2   3
   /
  4

以上二叉树会被序列化为 {1,2,3,#,#,4}

示例1

输入:
{1,2,2,3,4,4,3}
返回值:
true

示例2

输入:
{8,6,9,5,7,7,5}
返回值:
false

思路1


前序遍历递归:

  • 终止条件: 当进入子问题的两个节点都为空,说明都到了叶子节点,且是同步的,因此结束本次子问题,返回true;当进入子问题的两个节点只有一个为空,或是元素值不相等,说明这里的对称不匹配,同样结束本次子问题,返回false。
  • 递归: 每次同步递归比较节点一的左子树和节点二的右子树,以及节点一的右子树和节点二的左子树。

每日一题——对称的二叉树,算法,算法

解答代码1


/**
 * struct TreeNode {
 *  int val;
 *  struct TreeNode *left;
 *  struct TreeNode *right;
 *  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
  public:
    /**
     * @param pRoot TreeNode类
     * @return bool布尔型
     */
    bool isSymmetrical(TreeNode* pRoot) {
        // write code here
        if (pRoot == nullptr) {
            return true;
        }
        return isSymmetricalByRecursion(pRoot->left, pRoot->right);
    }

    bool isSymmetricalByRecursion(TreeNode* r1, TreeNode* r2) {
        // 终止条件:到叶子结点返回true
        if (r1 == nullptr && r2 == nullptr) {
            return true;
        }

        // 终止条件:节点值不等,或有一个节点为空,返回false
        if (r1->val != r2->val || r1 == nullptr || r2 == nullptr) {
            return false;
        }

        // 本层任务
        return isSymmetricalByRecursion(r1->left, r2->right) 
            && isSymmetricalByRecursion(r1->right, r2->left);
    }
};

思路2


通过bfs(广度优先)分别遍历根节点的左右子树,检查其对称性。从左往右遍历左子树,从右往左遍历右子树。

每日一题——对称的二叉树,算法,算法文章来源地址https://www.toymoban.com/news/detail-647918.html

解答代码2


/**
 * struct TreeNode {
 *  int val;
 *  struct TreeNode *left;
 *  struct TreeNode *right;
 *  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
#include <queue>
class Solution {
  public:
    /**
     * @param pRoot TreeNode类
     * @return bool布尔型
     */
    bool isSymmetrical(TreeNode* pRoot) {
        // write code here
        if (pRoot == nullptr) {
            return true;
        }
        // bfs辅助队列
        queue<TreeNode*> left;
        queue<TreeNode*> right;
        left.emplace(pRoot->left);
        right.emplace(pRoot->right);
        while (!left.empty() && !right.empty()) {
            auto r1 = left.front();
            left.pop();
            auto r2 = right.front();
            right.pop();
            if (r1 == nullptr && r2 == nullptr) {
                // 两个节点都为空,则进行下一轮检测
                continue;
            }
            if (r1->val != r2->val || r1 == nullptr || r2 == nullptr) {
                return false;
            }
            // 左队列从左往右加入子节点,右队列从右往左加入子节点
            left.emplace(r1->left);
            left.emplace(r1->right);
            right.emplace(r2->right);
            right.emplace(r2->left);
        }
        return true;
    }
};

到了这里,关于每日一题——对称的二叉树的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 每日一题 102二叉树的层序遍历

    给你二叉树的根节点 root ,返回其节点值的 层序遍历 。 (即逐层地,从左到右访问所有节点)。 示例 1: 输入:root = [3,9,20,null,null,15,7] 输出:[[3],[9,20],[15,7]] 示例 2: 输入:root = [1] 输出:[[1]] 示例 3: 输入:root = [] 输出:[] 提示: 树中节点数目在范围 [0, 2000] 内 -1000 =

    2024年02月09日
    浏览(38)
  • 每日一题 1372二叉树中的最长交错路径

    给你一棵以  root  为根的二叉树,二叉树中的交错路径定义如下: 选择二叉树中  任意  节点和一个方向(左或者右)。 如果前进方向为右,那么移动到当前节点的的右子节点,否则移动到它的左子节点。 改变前进方向:左变右或者右变左。 重复第二步和第三步,直到你

    2024年02月10日
    浏览(39)
  • 每日一题:LeetCode-102.二叉树的层序遍历

    前言: 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈    🔎🔎如果说代码有灵魂,那么它的灵魂一定是👉👉 算法 👈👈,因此,想要写出💚优美的程序💚,核心算法是必不可少的,少年,你渴望力量吗😆😆,想掌握程序的灵魂吗❓❗️那么就必须踏上这样一条漫长

    2024年02月05日
    浏览(35)
  • 236. 二叉树的最近公共祖先 ——【Leetcode每日一题】

    给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为:“对于有根树 T 的两个节点 p 、 q ,最近公共祖先表示为一个节点 x ,满足 x 是 p 、 q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。” 示例 1: 输入:root

    2023年04月26日
    浏览(27)
  • Leetcode-每日一题【剑指 Offer 27. 二叉树的镜像】

    请完成一个函数,输入一个二叉树,该函数输出它的镜像。 例如输入:      4    /     2     7  /   / 1   3 6   9 镜像输出:      4    /     7     2  /   / 9   6 3   1 示例 1: 输入: root = [4,2,7,1,3,6,9] 输出: [4,7,2,9,6,3,1] 限制: 0 = 节点个数 = 1000 1.题目要求我们设

    2024年02月13日
    浏览(36)
  • 每日一题:LeetCode-589.N叉树的前序遍历序列构造二叉树

    前言: 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈    🔎🔎如果说代码有灵魂,那么它的灵魂一定是👉👉 算法 👈👈,因此,想要写出💚优美的程序💚,核心算法是必不可少的,少年,你渴望力量吗😆😆,想掌握程序的灵魂吗❓❗️那么就必须踏上这样一条漫长

    2024年02月05日
    浏览(34)
  • (树) 剑指 Offer 27. 二叉树的镜像 ——【Leetcode每日一题】

    难度:简单 请完成一个函数,输入一个二叉树,该函数输出它的镜像。 例如输入: 镜像输出: 示例 1: 输入:root = [4,2,7,1,3,6,9] 输出:[4,7,2,9,6,3,1] 限制 : 0 = 节点个数 = 1000 注意 :本题与 226. 翻转二叉树 相同。 💡思路:递归 我们从根节点开始,递归地对树进行遍历: 如果

    2024年02月13日
    浏览(29)
  • 算法刷题Day 15 二叉树的层序遍历+翻转二叉树+对称二叉树

    层序遍历二叉树需要借助到队列 递归方法 迭代方法 就是简单的用上前序遍历迭代方法实现,不用想的太复杂 递归方法 迭代方法 这里使用了队列来存放两个要比较的结点。也可以使用栈,方法是类似的。

    2024年02月12日
    浏览(35)
  • Leetcode每日一题:1448. 统计二叉树中好节点的数目

    给你一棵根为  root  的二叉树,请你返回二叉树中好节点的数目。 「好节点」X 定义为:从根到该节点 X 所经过的节点中,没有任何节点的值大于 X 的值。 示例 1: 示例 2: 示例 3: 提示: 二叉树中节点数目范围是  [1, 10^5]  。 每个节点权值的范围是  [-10^4, 10^4]  。 显然

    2024年02月11日
    浏览(32)
  • 每日一题:leetcode 1448 统计二叉树中好节点的数目

    给你一棵根为  root  的二叉树,请你返回二叉树中好节点的数目。 「好节点」X 定义为:从根到该节点 X 所经过的节点中,没有任何节点的值大于 X 的值。 示例 1: 示例 2: 示例 3: 提示: 二叉树中节点数目范围是  [1, 10^5]  。 每个节点权值的范围是  [-10^4, 10^4]  。 思路

    2024年02月11日
    浏览(33)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包