- 相關推薦
C++編寫算法判斷兩棵二叉樹是否相等
筆試題目：C++編寫算法判斷兩棵二叉樹是否相等
題目：請實現兩棵樹是否相等的比較，相等返回0否則返回其他值。
解析：A、B兩棵樹相等，當且僅當RootA->c == RootB->c，而且A的左右子樹對應相等或者左右互換后相等。
思想是使用分治的方法，先判斷當前節點是否相等(需要處理為空、是否都為空、是否相等)，如果當前節點不相等，直接返回兩棵樹不相等;如果當前節點相等，那么就遞歸的判斷他們的左右孩子是否相等。因為這里是普通的二叉樹，所以A的左、右子樹和B的右、左子樹相等也是可以的。
C++代碼：
#include
using namespace std;
typedef struct TreeNode{
char c;
struct TreeNode * left;
struct TreeNode * right;
};
/*判斷兩棵二叉樹是否相等，如果相等返回0，如果不相等則返回1*/
int compareTree(TreeNode* tree1, TreeNode* tree2){
//用分治的方法做，比較當前根，然后比較左子樹和右子樹
bool tree1IsNull = (tree1==NULL);
bool tree2IsNull = (tree2==NULL);
if(tree1IsNull != tree2IsNull){
return 1;
}
if(tree1IsNull && tree2IsNull){
//如果兩個都是NULL，則相等
return 0;
}
//如果根節點不相等，直接返回不相等，否則的話，看看他們孩子相等不相等
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++編寫算法判斷兩棵二叉樹是否相等】相關文章：
判斷兒童的心理是否健康的標志05-08
怎么判斷是否是焦慮癥05-08
如何判斷面試是否成功11-19
如何判斷自己是否適合創業03-07
家電常識：如何判斷冰箱是否保鮮？07-14
如何判斷你是否適合創業呢12-21
DOS中判斷進程是否存在的方法03-09
創業初期如何判斷項目是否賺錢11-02
創業初期如何判斷項目是否賺錢03-05
怎么判斷咖啡豆是否新鮮01-04