【牛客刷题 - 算法】NC16 对称的二叉树

作者：清风莫追

2022 年 10 月 04 日
湖南
本文字数：1124 字
阅读完需：约 4 分钟

个人主页：CSDN清风莫追
系列专栏：牛客刷题——数据结构与算法
推荐一款面试、刷题神器牛客网：👉点击加入刷题大军👈

1.题目描述

描述给定一棵二叉树，判断其是否是自身的镜像（即：是否对称）例如：下面这棵二叉树是对称的

下面这棵二叉树不对称。

数据范围：节点数满足 $0 \leq n \leq 1000$ ，节点上的值满足 $∣ v a l ∣ \leq 1000$ 要求：空间复杂度 O(n)O(n)，时间复杂度 O(n)O(n)备注：你可以用递归和迭代两种方法解决这个问题

2.算法设计思路

我采用的递归方法。

对称的二叉树将具有一个特性：

根->左->右 和 根->右->左 的遍历方法，将得到相同的遍历序列。

而不对称的二叉树则不具有这样的特性（设遍历序列包含空的结点）。

算法过程：

采用 根->左->右 和 根->右->左 的顺序分别遍历二叉树，同时存下各自的遍历序列
逐个元素比较得到的两个序列
若序列相同，返回 true；否则返回 false

例如：对于二叉树

根->左->右 顺序遍历： $1,2,#,3,#,#,2,#,3,#,#$ 根->右->左 顺序遍历： $1,2,3,#,#,#,2,3,#,#,#$

3.算法实现

注：这里并不是完整代码，而只是核心代码的模式


/*struct TreeNode {    int val;    struct TreeNode *left;    struct TreeNode *right;    TreeNode(int x) :            val(x), left(NULL), right(NULL) {    }};*/const int BIG_NUM = 6666;//空结点处的填充值
class Solution {public:    //遍历二叉树，同时将遍历结果存入数组 a    //i:迭代数组a的下标，flag：决定遍历的顺序（从左到右、从右到左）    void scan(TreeNode* root, int & i, int a[], bool flag){        if(root ** NULL) {            a[i++] = BIG_NUM;            return;        }        a[i++] = root->val;        if(flag){            scan(root->left, i, a, flag);            scan(root->right, i, a, flag);        }        else{            scan(root->right, i, a, flag);            scan(root->left, i, a, flag);        }        return;    }    //判断传入的二叉树是否为自身的镜像    bool isSymmetrical(TreeNode* pRoot) {        int LR[2005] = {};//存放从左到右遍历，得到的序列        int RL[2005] = {};//存放从右到左遍历，得到的序列        int it_lr = 0;//对应的数组下标        int it_rl = 0;
        scan(pRoot, it_lr, LR, true);        scan(pRoot, it_rl, RL, false);
        for(int i = 0; i < it_lr; i++){            if(LR[i] != RL[i]){                return false;            }        }        return true;    }};

复制代码

4.运行结果

成功通过！

结束语：

今天的分享就到这里啦，快来加入刷题大军叭！👉点击开始刷题学习👈

感谢阅读

个人主页：CSDN清风莫追

发布于: 刚刚阅读数: 3

原文链接:【http://xie.infoq.cn/article/c971d766db2881ad475f8536a】。文章转载请联系作者。

清风莫追

关注

还未添加个人签名 2022.08.09 加入

编程一学生

发布

暂无评论

创作场景