C++編寫算法判斷兩棵二叉樹(shù)是否相等
筆試題目:C++編寫算法判斷兩棵二叉樹(shù)是否相等
題目:請(qǐng)實(shí)現(xiàn)兩棵樹(shù)是否相等的比較,相等返回0否則返回其他值,
C++編寫算法判斷兩棵二叉樹(shù)是否相等
。解析:A、B兩棵樹(shù)相等,當(dāng)且僅當(dāng)RootA->c == RootB->c,而且A的左右子樹(shù)對(duì)應(yīng)相等或者左右互換后相等。
思想是使用分治的'方法,先判斷當(dāng)前節(jié)點(diǎn)是否相等(需要處理為空、是否都為空、是否相等),如果當(dāng)前節(jié)點(diǎn)不相等,直接返回兩棵樹(shù)不相等;如果當(dāng)前節(jié)點(diǎn)相等,那么就遞歸的判斷他們的左右孩子是否相等。因?yàn)檫@里是普通的二叉樹(shù),所以A的左、右子樹(shù)和B的右、左子樹(shù)相等也是可以的。
C++代碼:
#include
using namespace std;
typedef struct TreeNode{
char c;
struct TreeNode * left;
struct TreeNode * right;
};
/*判斷兩棵二叉樹(shù)是否相等,如果相等返回0,如果不相等則返回1*/
int compareTree(TreeNode* tree1, TreeNode* tree2){
//用分治的方法做,比較當(dāng)前根,然后比較左子樹(shù)和右子樹(shù)
bool tree1IsNull = (tree1==NULL);
bool tree2IsNull = (tree2==NULL);
if(tree1IsNull != tree2IsNull){
return 1;
}
if(tree1IsNull && tree2IsNull){
//如果兩個(gè)都是NULL,則相等
return 0;
}
//如果根節(jié)點(diǎn)不相等,直接返回不相等,否則的話,看看他們孩子相等不相等
if(tree1->c != tree2->c){
return 1;
}
return (compareTree(tree1->left,tree2->left)&compareTree(tree1->right,tree2->right))
|
(compareTree(tree1->left,tree2->right)&compareTree(tree1->right,tree2->left))
;
}
【C++編寫算法判斷兩棵二叉樹(shù)是否相等】相關(guān)文章:
6.判斷簡(jiǎn)歷中“自我評(píng)價(jià)”是否合格的3個(gè)標(biāo)準(zhǔn)
7.C++筆試