对称的二叉树

C 解法, 执行用时: 3ms, 内存消耗: 408KB, 提交时间: 2021-12-23

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param pRoot TreeNode类 
 * @return bool布尔型
 */
bool is_same(struct TreeNode* root1,struct TreeNode* root2)
{
    if(NULL == root1 && NULL == root2)    return true;
    if(NULL == root1 || NULL == root2)    return false;
    return root1->val == root2->val && is_same(root1->left,root2->right) && is_same(root2->left,root1->right);
}

bool isSymmetrical(struct TreeNode* pRoot ) {
    // write code here
    return is_same(pRoot,pRoot);
}

C 解法, 执行用时: 3ms, 内存消耗: 412KB, 提交时间: 2022-06-09

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param pRoot TreeNode类 
 * @return bool布尔型
 */
#include<stdbool.h>
typedef struct stackNode{
    struct TreeNode* node;
    struct stackNode* next;
}stackNode, *stackNodePtr;
typedef struct QueueList{
    stackNodePtr front, rear;
    int count;
}QueueList;
static QueueList *stackCreate(){
    QueueList *Q = (QueueList *)malloc(sizeof(QueueList));
    Q->front = (stackNodePtr)malloc(sizeof(stackNode));
    Q->front->next = NULL;
    Q->rear = Q->front;
    Q->count = 0;
    return Q;
}
static void EnQueue(QueueList *Q, struct TreeNode *e ){
    stackNodePtr p = (stackNodePtr)malloc(sizeof(stackNode));
    p->node = e;
    p->next = NULL;
    Q->rear->next = p;
    Q->rear = p;
    Q->count++;
}
static void DeQueue(QueueList *Q){
    if(Q->front == Q->rear)
        return;
    stackNodePtr p;
    p = Q->front->next;
    Q->front->next = p->next;
    if(Q->rear == p)
        Q->rear = Q->front;
    Q->count--;
    free(p);
}
static bool satckIsEmpty(QueueList *Q){
    if(Q->front == Q->rear)
        return true;
    return false;
}
bool isSymmetrical(struct TreeNode* pRoot ) {
    // write code here
    if(pRoot == NULL)
        return true;
    
    struct TreeNode *cur1;
    struct TreeNode *cur2;
    QueueList *Q1 = stackCreate();
    QueueList *Q2 = stackCreate();
    EnQueue(Q1, pRoot->left);
    EnQueue(Q2, pRoot->right);
    while(!satckIsEmpty(Q1) && !satckIsEmpty(Q2)){
        cur1 = Q1->front->next->node;
        DeQueue(Q1);
        cur2 = Q2->front->next->node;
        DeQueue(Q2);
        if(cur1 == NULL && cur2 == NULL)
            continue;
        if(cur1 == NULL || cur2 == NULL || cur1->val != cur2->val)
            return false;
        EnQueue(Q1, cur1->left);
        EnQueue(Q1, cur1->right);
        
        EnQueue(Q2, cur2->right);
        EnQueue(Q2, cur2->left);
    }
    return true;
}

C 解法, 执行用时: 3ms, 内存消耗: 412KB, 提交时间: 2022-04-13

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param pRoot TreeNode类 
 * @return bool布尔型
 */
#include<stdbool.h>
bool fun(struct TreeNode* p,struct TreeNode* q)
{    
    if(NULL==p&&NULL==q) return true;
    if(NULL==p||NULL==q) return false;
    if(p->val!=q->val) return false;
    bool L=fun(p->left,q->right);
    bool R=fun(p->right,q->left);
    return L&&R;
}
/*
bool fun(struct TreeNode *left,struct TreeNode *right)
{
    if(left == NULL && right == NULL)
        return true;
    if(left == NULL || right == NULL)
        return false;
    if(left->val != right->val)
        return false;
    bool L = fun(left->left,left->right);
    bool R = fun(right->left,right->right);
    return L&&R;
}
*/
bool isSymmetrical(struct TreeNode* pRoot ) {
    // write code here
    if(pRoot == NULL)
        return true;
    
    return fun(pRoot->left,pRoot->right);
}

C 解法, 执行用时: 3ms, 内存消耗: 412KB, 提交时间: 2021-11-23

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param pRoot TreeNode类 
 * @return bool布尔型
 */
bool comRoot(struct TreeNode *pLeft,struct TreeNode *pRight)
{ 
        if(pLeft == NULL) return pRight == NULL;
        if(pRight == NULL) return false;
        if(pLeft->val != pRight->val) return false;
        return comRoot(pLeft->right,pRight->left) && comRoot(pLeft->left,pRight->right);
        
}
bool isSymmetrical(struct TreeNode* pRoot ) {
    // write code here
    if(pRoot == NULL) return true;
    return comRoot(pRoot->left,pRoot->right);
}

C 解法, 执行用时: 3ms, 内存消耗: 416KB, 提交时间: 2022-05-29

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param pRoot TreeNode类 
 * @return bool布尔型
 */
bool check(struct TreeNode*left,struct TreeNode*right)
{
    if(left==NULL&&right==NULL)return true;
    if(left==NULL&&right!=NULL)return false;
    if(left!=NULL&&right==NULL)return false;
    if(left->val==right->val) {
        return check(left->left,right->right)&&check(left->right,right->left);
    }
    return false;
}

bool isSymmetrical(struct TreeNode* pRoot ) {
    if(pRoot==NULL)return true;
     
    return check(pRoot->left, pRoot->right);
}

详情