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

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

题目


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

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

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

下面这棵二叉树不对称。

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

数据范围:节点数满足 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模板网!

原文地址:https://blog.csdn.net/caesar1228/article/details/132287606

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

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

相关文章

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包