例如: 下面这棵二叉树是对称的
下面这棵二叉树不对称。
数据范围:节点数满足 ,节点上的值满足
要求:空间复杂度 ,时间复杂度
备注:
你可以用递归和迭代两种方法解决这个问题
bool IS(struct TreeNode*l,struct TreeNode*r) { //若左右都为遍历完 if(!l&&!r) { return true; } //若不对称,左空右存,左存右空,左右不相等 if(!l||!r||l->val!=r->val) { return false; } return IS(l->left,r->right)&&IS(l->right,r->left); } bool isSymmetrical(struct TreeNode* pRoot ) { // write code here //若根节点为空 if(!pRoot) { return true; } //遍历根节点的左右子节点 return IS(pRoot->left,pRoot->right); }
有点偷懒的办法
层序遍历然后直接扫描
bool isSymmetrical(struct TreeNode* pRoot ) { if(pRoot==NULL){ return true; } struct TreeNode* nodelist[1500]; int i = 0; int j = 1; nodelist[0] = pRoot; while (i<j) { int left = i; int right = j-1; while(i<right+1){ if(nodelist[i]!=NULL){ nodelist[j++] = nodelist[i]->left; nodelist[j++] = nodelist[i]->right; } i++; } while(left<right){ if(nodelist[left]!=NULL&&nodelist[right]!=NULL){ if(nodelist[left]->val != nodelist[right]->val){ return false; } }else if(nodelist[left]==NULL&&nodelist[right]==NULL); else{ return false; } left++; right--; } } return true; }
int judge(struct TreeNode* p,struct TreeNode* q){ if(!p && q) return false; if(p && !q) return false; if(!p && !q) return true; if(p->val == q->val) return judge(p->left,q->right)&&judge(p->right,q->left); else return false; } bool isSymmetrical(struct TreeNode* pRoot ) { // write code here if(!pRoot) return true; return judge(pRoot->left,pRoot->right); }
#define MAXQSIZE 512 struct TreeNode{ int val; struct TreeNode* left; struct TreeNode* right; }; typedef struct TreeNode TreeNode; TreeNode* createBiTree(int arr[],int n,int index){ if(index>=n || arr[index]==NULL) return NULL; TreeNode* root=(TreeNode*)malloc(sizeof(TreeNode)); root->val=arr[index]; root->left=createBiTree(arr,n,index*2+1); root->right=createBiTree(arr,n,index*2+2); return root; } int isHuiWenChuan(int arr[],int n){ int left=0,right=n-1; while(left<=right){ if(arr[left]!=arr[right]) return 0; left++; right--; } return 1; } bool isSymmetrical(struct TreeNode* pRoot ) { TreeNode* r=pRoot; TreeNode* queue[MAXQSIZE]; int front=0,rear=0; queue[rear]=r; rear=(rear+1)%MAXQSIZE; int size;//层序遍历实现每层控制,需要size TreeNode* node; int *arr=(int *)malloc(sizeof(int)); int sum,p,num; while(front!=rear){ num=p=0;//辅助数组大小及指针 sum=size=(rear-front+MAXQSIZE)%MAXQSIZE; while(size>0){//每一层 num++; arr=(int *)realloc(arr,sizeof(int)*num); node=queue[front]; arr[p++]=node!=NULL?node->val:-1;//当前层的结点值入辅助数组 front=(front+1)%MAXQSIZE; if(node!=NULL){ queue[rear]=node->left; rear=(rear+1)%MAXQSIZE; queue[rear]=node->right; rear=(rear+1)%MAXQSIZE; } size--; }//while size if(isHuiWenChuan(arr,sum)==0) return false; memset(arr,NULL,sizeof(int)*sum);//清空数组 }//while queue return true; } /* bool checkLR(TreeNode* L,TreeNode* R){ if(L==NULL && R==NULL) return true; if((L!=NULL&&R==NULL) || (L==NULL&&R!=NULL)) return false; return L->val==R->val && checkLR(L->left,R->right) && checkLR(L->right,R->left); } bool isSymmetric(struct TreeNode* root ) { return checkLR(root->left,root->right); }*/