例如： 下面这棵二叉树是对称的
下面这棵二叉树不对称。
数据范围：节点数满足 
，节点上的值满足 
要求：空间复杂度 )
，时间复杂度
备注：
你可以用递归和迭代两种方法解决这个问题
[编程题]对称的二叉树
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);
}
发表于 2023-11-16 15:37:00
回复(0)
有点偷懒的办法
层序遍历然后直接扫描
理论上写个循环队列或者双队列空间会更小一些？
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;
}
发表于 2023-09-21 21:49:26
回复(0)
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param pRoot TreeNode类
* @return bool布尔型
*/
bool isSymmetrical(struct TreeNode* pRoot )
{
// write code here
if(!pRoot)
{
return true;
}
struct TreeNode*T[500];
int front=0;
int rear=0;
T[front++]=pRoot;
while(T[rear])
{
T[front++]=NULL;
int i=rear;
int j=front-2;
while(i<j)
{
if(T[i]->val!=T[j]->val)
{
return false;
}
++i;
--j;
}
int t=front-2;
while(T[rear])
{
if(T[rear]->left)
{
if(!T[t]->right)
{
return false;
}
T[front++]=T[rear]->left;
}
if(T[rear]->right)
{
if(!T[t]->left)
{
return false;
}
T[front++]=T[rear]->right;
}
++rear;
--t;
}
++rear;
}
return true;
}
发表于 2023-07-08 19:49:24
回复(0)
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);
}
发表于 2023-03-26 22:32:16
回复(0)
//自己的方法行不通！！！ 不能用两次遍历判断！
#include <stdbool.h>
typedef struct TreeNode TNode ;
bool check(TNode *p, TNode *q);
bool isSymmetrical(struct TreeNode* pRoot ) {
if (pRoot == NULL) return true;
return check(pRoot->left, pRoot->right);
}
bool check(TNode *p, TNode *q){
if (p == NULL && q == NULL) return true;
if (p == NULL || q == NULL || p->val != q->val) return false;
return check(p->left, q->right) && check(p->right, q->left);
}
发表于 2023-03-15 11:06:40
回复(0)
深度或者广度，深度就是依次遍历p,q的邻接点判断是否相等，p,q初始为根的左右结点；广度就是层次遍历。
#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);
}*/
发表于 2023-03-10 10:35:47
回复(0)
#include<stdbool.h>
bool _is_sym(struct TreeNode* r1,struct TreeNode* r2)
{
if(NULL==r1&&NULL==r2)return true;
if(NULL==r1&&r2!=NULL)return false;
if(NULL!=r1&&r2==NULL)return false;
if(r1->val != r2->val)return false;
return _is_sym(r1->left,r2->right) && _is_sym(r1->right,r2->left);
}
bool isSymmetrical(struct TreeNode* pRoot ) {
// write code here
if(NULL==pRoot)return true;
return _is_sym(pRoot->left,pRoot->right);
}
bool _is_sym(struct TreeNode* r1,struct TreeNode* r2)
{
if(NULL==r1&&NULL==r2)return true;
if(NULL==r1&&r2!=NULL)return false;
if(NULL!=r1&&r2==NULL)return false;
if(r1->val != r2->val)return false;
return _is_sym(r1->left,r2->right) && _is_sym(r1->right,r2->left);
}
bool isSymmetrical(struct TreeNode* pRoot ) {
// write code here
if(NULL==pRoot)return true;
return _is_sym(pRoot->left,pRoot->right);
}
发表于 2022-08-15 20:23:18
回复(0)
问题信息
通过挑战的用户
-
2023-02-21 16:04:31 -
2023-02-13 22:11:16 -
2022-10-16 16:18:27
-
2022-09-16 21:04:24 -
2022-09-16 18:19:08
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
/*思路：首先根节点以及其左右子树，左子树的左子树和右子树的右子树相同 * 左子树的右子树和右子树的左子树相同即可，采用递归 * 非递归也可，采用栈或队列存取各级子树根节点 */ public class Solution { boolean isSymmetrical(TreeNode pRoot) { if(pRoot == null){ return true; } return comRoot(pRoot.left, pRoot.right); } private boolean comRoot(TreeNode left, TreeNode right) { // TODO Auto-generated method stub if(left == null) return right==null; if(right == null) return false; if(left.val != right.val) return false; return comRoot(left.right, right.left) && comRoot(left.left, right.right); } }