對稱的二叉樹

對稱的二叉樹

實現一個函數，判斷一顆二叉樹是不是對稱的。

如果二叉樹和它的鏡像是一樣的，則是對稱的。

思路：對先序遍歷定義一種對稱的遍歷演算法，

參考代碼：

root@gt:/home/git/Code# ./a.out 1root@gt:/home/git/Code# cat isSymmetry.c #include <stdio.h>#include <stdlib.h>#include <string.h>typedef struct BinaryTreeNode{ int value; struct BinaryTreeNode* pLeft; struct BinaryTreeNode* pRight;}BTNode;int core(BTNode* root1,BTNode* root2){ if(root1 == NULL && root2 == NULL) return 1; if(root1 == NULL || root2 == NULL) return 0; if(root1->value != root2->value) return 0; return core(root1->pLeft,root2->pRight) && core(root1->pRight,root2->pLeft);}int isSymmetry(BTNode* root){ return core(root,root);}BTNode* concore(int* preStart,int* preEnd,int* inStart,int* inEnd){//前序遍歷的地一個元素就是根節點 int rootValue = preStart[0]; BTNode* root = malloc(sizeof(BTNode)); root->value = rootValue; root->pLeft = root->pRight = NULL;//在中序遍歷序號中找到根節點的值 int* rootIn = inStart; while(rootIn <= inEnd && *rootIn != rootValue) ++rootIn; int leftLen = rootIn - inStart; int* leftPreEnd = preStart + leftLen; if(leftLen>0) { root->pLeft = concore(preStart+1,leftPreEnd,inStart,inStart+leftLen-1); } if(leftLen < preEnd - preStart) { root->pRight = concore(leftPreEnd+1,preEnd,rootIn+1,inEnd); } return root;}BTNode* construct(int* pre,int* in,int len){ if(pre==NULL || in==NULL || len<=0) return 0; return concore(pre,pre+len-1,in,in+len-1);}void preOrder(BTNode* root){ if(root ==NULL) return; printf("%d ",root->value); preOrder(root->pLeft); preOrder(root->pRight);}int main(){ int pre[] = {8,6,5,7,6,7,5}; int in[] = {5,6,7,8,7,6,5}; BTNode* root = construct(pre,in,sizeof(pre)/sizeof(int)); int res = isSymmetry(root); printf("%d
",res); return 0;}

推薦閱讀：