对称的二叉树
方法一
递归
分别用两个指针L和R分别指向对称的两个子树的对称的结点。
如果L和R均为空，对称，返回true
如果L和R一个为空一个不为空，则不对称，返回false
如果L和R均不为空则判断L和R指向结点的值是否相等，如果不等返回false
如果L和R指向结点的值相等
递归。L指向其左孩子，R指向其右孩子。记录返回值
递归。L指向其右孩子，R指向其左孩子。记录返回值
如果两次返回值都为真返回true，否则返回false。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
bool check(struct TreeNode* L,struct TreeNode* R){
if(!L && !R){
return true;
}
else if((!L && R) ||(L && !R)){
return false;
}
else if(L->val == R->val){
//如果需要L指向左子树，R指向右子树
//将下面两个check交换位置即可
//因为第一次LR相同，比较后会造成L和R指向的子树改变。
if(check(L->left,R->right) && check(L->right,R->left)){
return true;
}
else{
return false;
}
}
else{
return false;
}
}
bool isSymmetric(struct TreeNode* root){
//第一次传入时会有一次重复比较,因为右子树先右后左，会造成第一次比
//较过后实际上L是在指向右子树,R指向右子树。
//如果需要L指向左子树,R指向右子树。
//只需每次递归L先访问右子树，后访问左子树。
return check(root,root);
}
根结点分开比较，从而L就是一直指向左子树，R指向右子树。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
bool check(struct TreeNode* L,struct TreeNode* R){
if(!L && !R){
return true;
}
else if((!L && R) ||(L && !R)){
return false;
}
else if(L->val == R->val){
if(check(L->left,R->right) && check(L->right,R->left)){
return true;
}
else{
return false;
}
}
else{
return false;
}
}
bool isSymmetric(struct TreeNode* root){
if(root){
return check(root->left,root->right);
}
else{
return true;
}
}
方法二
迭代
可以用栈，也可以用队列。
先将对应位置的结点压入栈，每次弹栈弹出两个结点。分别用L和R两个指针临时保存。
进行判断，若L和R同时为空则说明分支到底，为叶子结点。所以直接出栈就行。
否则判断L和R是否为一空一不空。如果是则不对称return false。如果都不为空则判断L和R指向的值是否相等，如果则不对称，如果相等则将两个结点的孩子按照对应位置压栈，如L右R左，或者L左R右都可以。总之与弹栈的顺序相反。
栈
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
struct Stack{
struct TreeNode** data;
int top;
};
int StackPush(struct Stack* S,struct TreeNode* T){
*(S->data + S->top) = T;
S->top++;
return 1;
}
int StackPop(struct Stack* S,struct TreeNode** T){
S->top--;
*T = *(S->data + S->top);
return 1;
}
bool isSymmetric(struct TreeNode* root){
//先判断根结点是否为空
if(root){
struct Stack* S = (struct Stack*)malloc(sizeof(struct Stack));
S->data = (struct TreeNode**)malloc(sizeof(struct TreeNode*)*1000);
S->top = 0;
//如果根结点不为空，将左孩子和右孩子分别压栈
StackPush(S,root->left);
StackPush(S,root->right);
while(S->top){
struct TreeNode* L;
struct TreeNode* R;
StackPop(S,&R);
StackPop(S,&L);//将一对位置的结点出栈
if(!(!L && !R)){//如果结点不全为空则进行比较
if((!L && R) || (L && !R)){//一空一不空，不对称
free(S->data);
free(S);
return false;
}
else if(L->val == R->val){//都不空，比较值，相等压栈
StackPush(S,L->right);
StackPush(S,R->left);
StackPush(S,L->left);
StackPush(S,R->right);
}
else{//不等，不对称
free(S->data);
free(S);
return false;
}
}
}
free(S->data);
free(S);
return true;
}
else{
return true;
}
}
//栈的另外表示方法
//用指针表示栈顶
/**
// * Definition for a binary tree node.
// * struct TreeNode {
// * int val;
// * struct TreeNode *left;
// * struct TreeNode *right;
// * };
// */
// struct Stack{
// struct TreeNode** data;
// struct TreeNode** top;
// };
// int StackPush(struct Stack* S,struct TreeNode* T){
// if(S->top - S->data == 1000){
// return 0;
// }
// else{
// *S->top = T;
// S->top++;
// return 1;
// }
// }
// int StackPop(struct Stack* S,struct TreeNode** T){
// if(S->top == S->data){
// return 0;
// }
// else{
// S->top--;
// *T = *S->top;
// return 1;
// }
// }
// bool isSymmetric(struct TreeNode* root){
// if(root){
// struct Stack* S = (struct Stack*)malloc(sizeof(struct Stack));
// S->data = (struct TreeNode**)malloc(sizeof(struct TreeNode*)*1000);
// S->top = S->data;
// StackPush(S,root->left);
// StackPush(S,root->right);
// while(S->top != S->data){
// struct TreeNode* L;
// struct TreeNode* R;
// StackPop(S,&R);
// StackPop(S,&L);
// if(!(!L && !R)){
// if((!L && R) || (L && !R)){
// free(S->data);
// free(S);
// return false;
// }
// else if(L->val == R->val){
// StackPush(S,L->right);
// StackPush(S,R->left);
// StackPush(S,L->left);
// StackPush(S,R->right);
// }
// else{
// free(S->data);
// free(S);
// return false;
// }
// }
// }
// free(S->data);
// free(S);
// return true;
// }
// else{
// return true;
// }
// }
队列
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
struct Queue{
struct TreeNode** data;
int head;
int rear;
};
int QueueIn(struct Queue* Q,struct TreeNode* T){
*(Q->data + Q->rear) = T;
Q->rear++;
return 1;
}
int QueueOut(struct Queue* Q,struct TreeNode** T){
*T = *(Q->data + Q->head);
Q->head++;
return 1;
}
bool isSymmetric(struct TreeNode* root){
if(root){
struct Queue* Q = (struct Queue*)malloc(sizeof(struct Queue));
Q->data = (struct TreeNode**)malloc(sizeof(struct TreeNode*)*1000);
Q->head = 0;
Q->rear = 0;
//入队
QueueIn(Q,root->left);
QueueIn(Q,root->right);
while(Q->rear - Q->head){
struct TreeNode* L;
struct TreeNode* R;
QueueOut(Q,&L);
QueueOut(Q,&R);
if(!(!L && !R)){
if((!L && R) || (L && !R)){
free(S->data);
free(S);
return false;
}
else if(L-> val == R->val){
QueueIn(Q,L->right);
QueueIn(Q,R->left);
QueueIn(Q,L->left);
QueueIn(Q,R->right);
}
else{
free(S->data);
free(S);
return false;
}
}
}
free(S->data);
free(S);
return true;
}
else{
return true;
}
}
//改良队列
/**
// * Definition for a binary tree node.
// * struct TreeNode {
// * int val;
// * struct TreeNode *left;
// * struct TreeNode *right;
// * };
// */
// struct Queue{
// struct TreeNode** data;
// struct TreeNode** head;
// struct TreeNode** rear;
// };
// int QueueIn(struct Queue* Q,struct TreeNode* T){
// if(Q->rear - Q->data == 1000){
// return 0;
// }
// else{
// *Q->rear = T;
// Q->rear++;
// return 1;
// }
// }
// int QueueOut(struct Queue* Q,struct TreeNode** T){
// if(Q->rear == Q->head){
// return 0;
// }
// else{
// *T = *Q->head;
// Q->head++;
// return 1;
// }
// }
// bool isSymmetric(struct TreeNode* root){
// if(root){
// struct Queue* Q = (struct Queue*)malloc(sizeof(struct Queue));
// Q->data = (struct TreeNode**)malloc(sizeof(struct TreeNode*)*1000);
// Q->head = Q->data;
// Q->rear = Q->data;
// QueueIn(Q,root->left);
// QueueIn(Q,root->right);
// while(Q->head != Q->rear){
// struct TreeNode* L;
// struct TreeNode* R;
// QueueOut(Q,&L);
// QueueOut(Q,&R);
// if(!(!L && !R)){
// if((!L && R) || (L && !R)){
// free(Q->data);
// free(Q);
// return false;
// }
// else if(L->val == R->val){
// QueueIn(Q,L->right);
// QueueIn(Q,R->left);
// QueueIn(Q,L->left);
// QueueIn(Q,R->right);
// }
// else{
// free(Q->data);
// free(Q);
// return false;
// }
// }
// }
// free(Q->data);
// free(Q);
// return true;
// }
// else{
// return true;
// }
// }
本文含有隐藏内容，请 开通VIP 后查看