当前位置：首页 > news >正文

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

news 来源：原创 2024/5/4 5:24:35

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

文章目录

1.题目描述
2.算法设计思路
3.算法实现
4.运行结果
结束语：

1.题目描述

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

下面这棵二叉树不对称。
在这里插入图片描述

数据范围：节点数满足 $\le n \le 1000$ ，节点上的值满足 $\le 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;
    }
};