力扣101 对称二叉树 + 力扣 100 相同的树

给定一个二叉树，检查它是否是镜像对称的。

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

1
           

/

2 2

/ \ /

3 4 4 3

但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

1
           

/

2 2

\

3 3

用递归

基本思想：

抛开根结点，从左右子树出发，递归

两种思考方式：

1.从false方面出发，

在左右子树均存在时，

若r1->val!=r2->val false

若左右子树根节点相等但其子结点不对称 false

其他 true

在左右子树都无则true

左右子树其中一个无 false

代码：

bool Symmetric(struct TreeNode* p, struct TreeNode* q)
{
    if(p!=NULL&&q!=NULL)
    {
        if(p->val!=q->val)
        {
            return false;
        }
        else if(Symmetric(p->left, q->right)==false)
        {
            return false;
        }
        else if(Symmetric(p->right, q->left)==false)
        {
            return false;
        }
        else
        {
            return true;
        }
    }
    else if(p==NULL&&q==NULL)
    {
        return true;
    }
    else
    {
        return false;
    }
   
}

bool isSymmetric(struct TreeNode* root){
    if(root!=NULL)
    {
        return Symmetric(root->left,root->right);
    }
    else
    {
        return true;
    }
}
           

2.从true出发

在左右子树均存在

若r1->val==r2->val&&调用函数递归左右子树结点对称 true

在左右子树都无则true

左右子树其中一个无 false

代码：

bool isSymmetric(struct TreeNode* root){
    
    return isMirror(root, root);
}

int isMirror(struct TreeNode* r1, struct TreeNode* r2)
{
    if (r1 == NULL && r2 == NULL) return true;
    if (r1 == NULL || r2 == NULL) return false;

    return    (r1->val == r2->val)   &&
           isMirror(r1->left,  r2->right) &&
           isMirror(r1->right, r2->left);
}

           

显而易见，从true出发更简便。

带main函数的：

#include <stdio.h>
#include <stdlib.h>

typedef struct BTNode{
    int data;
    struct BTNode *lChild;
    struct BTNode *rChild;
}BiTNode;
//先序创建二叉树
int CreateBiTree(BiTNode **T)
{
    int ch;
    scanf("%d",&ch);
    if (ch ==-1)
    {
        *T = NULL;
        return 0;
    }
    else
    {
        *T = (BiTNode *)malloc(sizeof(BiTNode));
        if (T == NULL)
        {
            printf("failed\n");
            return 0;
        }
        else
        {
            (*T)->data = ch;
            printf("输入%d的左子节点：",ch);
            CreateBiTree(&((*T)->lChild));
            printf("输入%d的右子节点：",ch);
            CreateBiTree((&(*T)->rChild));
        }
    }

    return 1;
}
int isMirror(BiTNode* r1, BiTNode* r2)
{
	if (r1 == NULL && r2 == NULL) return 1;
	if (r1 == NULL || r2 == NULL) return 0;
	return (r1->data == r2->data) &&
		isMirror(r1->lChild, r2->rChild) &&
		isMirror(r1->rChild, r2->lChild);
}
//中序遍历二叉树
void MiddleOrderBiTree(BiTNode *T)
{
    if (T == NULL)
    {
        return;
    }
    else
    {
        MiddleOrderBiTree(T->lChild);
        printf("%d ",T->data);
        MiddleOrderBiTree(T->rChild);
    }
}
//主函数
int main(int argc,const char *argv[])
{
    BiTNode *T;

    printf("请输入第一个节点的值，-1表示没有叶节点：\n");
    CreateBiTree(&T);

    printf("中序遍历二叉树：");
    MiddleOrderBiTree(T);
    printf("\n");
	int a = isMirror(T, T);

	if (a) printf("true");
	else printf("false");

    return 0;
}
           

100 相同的树

此题与上题基本相同，只是不用抛开根节点，且两树是完全相同

不需要两个函数

代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */


bool isSameTree(struct TreeNode* p, struct TreeNode* q){
    if(p==NULL&&q==NULL) return true;
    if(p==NULL||q==NULL) return false;
  
     return (p->val==q->val)&&isSameTree(p->left,q->left)&&isSameTree(p->right,q->right);
   
}