判斷二叉樹(shù)B是否是二叉樹(shù)A的子樹(shù)或子結(jié)構(gòu)师脂。
定義區(qū)別
- 子樹(shù)：若B是A的子樹(shù)乡数，則A包含B的所有結(jié)點(diǎn)晚唇，并且B的葉子節(jié)點(diǎn)就是A的葉子節(jié)點(diǎn)。也就是A只要包含了B的一個(gè)結(jié)點(diǎn)杨何，就得包含這個(gè)結(jié)點(diǎn)下的所有節(jié)點(diǎn)酱塔。
- 子結(jié)構(gòu)：若B是A的子結(jié)構(gòu)，則A包含B的所有結(jié)點(diǎn)危虱，但B的葉子節(jié)點(diǎn)不一定是A的葉子節(jié)點(diǎn)羊娃。也就是子結(jié)構(gòu)B是A樹(shù)的任意一部分。
例如上面這棵樹(shù)埃跷，4->1是A的子結(jié)構(gòu)但不是子樹(shù)蕊玷，因?yàn)椴话?這個(gè)節(jié)點(diǎn)邮利；4->1->2是A的子樹(shù)，包含了節(jié)點(diǎn)4下的所有節(jié)點(diǎn)垃帅。
需要約定的是延届，空樹(shù)不是任何一棵樹(shù)的子樹(shù)或子結(jié)構(gòu)。
子樹(shù)判斷
判斷B是不是A的子樹(shù)贸诚，需要在A中找B方庭。先遍歷A樹(shù)，遇到節(jié)點(diǎn)值和B樹(shù)根節(jié)點(diǎn)相同時(shí)的節(jié)點(diǎn)時(shí)酱固，判斷它下面的節(jié)點(diǎn)是不是和B相同械念，這里就可以用一個(gè)遞歸函數(shù)來(lái)實(shí)現(xiàn)。遞歸函數(shù)的作用是：輸入兩個(gè)節(jié)點(diǎn)运悲，判斷以這兩個(gè)節(jié)點(diǎn)為根節(jié)點(diǎn)的樹(shù)是否完全相同龄减。
若在A中找到了這樣一個(gè)節(jié)點(diǎn)，和B樹(shù)的值完全相同班眯，則B就是A的子樹(shù)欺殿。
//主函數(shù)，判斷pRoot2是不是pRoot1的子樹(shù)
bool HasSubTree(TreeNode* pRoot1, TreeNode* pRoot2)
{
//若兩個(gè)樹(shù)有任意一個(gè)為空樹(shù)鳖敷，直接返回false
if (!pRoot1 || !pRoot2) return false;
//如果pRoot1的根節(jié)點(diǎn)和pRoot2的根節(jié)點(diǎn)值相同，就需要判斷這兩棵樹(shù)剩下的部分是否相同程拭，所以調(diào)用遞歸函數(shù)IsSametree
if (pRoot1->val == pRoot2->val)
return IsSametree(pRoot1, pRoot1);
//如果pRoot1的根節(jié)點(diǎn)和pRoot2的根節(jié)點(diǎn)值不同定踱，那么需要往下遍歷A樹(shù)，找它的左右節(jié)點(diǎn)恃鞋，有任意一個(gè)節(jié)點(diǎn)滿(mǎn)足條件時(shí)崖媚，B就是A的子樹(shù)
else
return HasSubTree(pRoot1->left, pRoot2) || HasSubTree(pRoot1->right, pRoot2);
}
//調(diào)用函數(shù)，判斷以這兩個(gè)節(jié)點(diǎn)為根節(jié)點(diǎn)的樹(shù)是否完全相同
bool IsSametree(TreeNode* pRoot1, TreeNode* pRoot2)
{
//如果兩個(gè)節(jié)點(diǎn)同時(shí)為空恤浪，則是相同的樹(shù)
if (!pRoot1 && !pRoot2) return true;
//如果兩個(gè)節(jié)點(diǎn)不同時(shí)為空畅哑，則肯定不是相同的樹(shù)
if (!pRoot1 || !pRoot2) return false;
//兩個(gè)節(jié)點(diǎn)都有值，但節(jié)點(diǎn)值不同水由，那肯定不是相同的樹(shù)
if (pRoot1->val != pRoot2->val)
return false;
//如果值相同荠呐，則判斷他們的左右節(jié)點(diǎn)是否也相同（必須都相同才行）
else
return IsSametree(pRoot1->left,pRoot2->left) && IsSametree(pRoot1->right,pRoot2->right);
}
子結(jié)構(gòu)判斷
判斷子結(jié)構(gòu)，條件會(huì)略微寬松一些砂客，因?yàn)橹灰狟是A的一部分就好泥张。同樣的遍歷A樹(shù)，找到和B根節(jié)點(diǎn)值相同的節(jié)點(diǎn)鞠值，再去判斷這個(gè)節(jié)點(diǎn)下面是不是包含B媚创。判斷是不是包含B的時(shí)候，要以B為靶子彤恶，也就是B節(jié)點(diǎn)為空了都行钞钙，但是不能出現(xiàn)節(jié)點(diǎn)值和B不一樣鳄橘，只要值不一樣，那就不是子結(jié)構(gòu)芒炼。這里遞歸函數(shù)的作用是：輸入兩個(gè)節(jié)點(diǎn)瘫怜，判斷判斷以這兩個(gè)節(jié)點(diǎn)為根節(jié)點(diǎn)的樹(shù)是否是包含關(guān)系。
若在A中找到了這樣一個(gè)節(jié)點(diǎn)焕议，能夠包含B樹(shù)宝磨，則B就是A的子結(jié)構(gòu)。
//主函數(shù)盅安，判斷pRoot2是不是pRoot1的子結(jié)構(gòu)
bool HasSubStructure(TreeNode* pRoot1, TreeNode* pRoot2)
{
//若兩個(gè)樹(shù)有任意一個(gè)為空樹(shù)唤锉，直接返回false
if (!pRoot1 || !pRoot2) return false;
//如果pRoot1的根節(jié)點(diǎn)和pRoot2的根節(jié)點(diǎn)值相同，就需要判斷這兩棵樹(shù)剩下的部分是否是包含關(guān)系别瞭，所以調(diào)用遞歸函數(shù)IsSametree
if (pRoot1->val == pRoot2->val)
return IsSametree(pRoot1, pRoot1);
//如果pRoot1的根節(jié)點(diǎn)和pRoot2的根節(jié)點(diǎn)值不同窿祥，那么需要往下遍歷A樹(shù)，找它的左右節(jié)點(diǎn)蝙寨，有任意一個(gè)節(jié)點(diǎn)滿(mǎn)足條件時(shí)晒衩，B就是A的子樹(shù)
else
return HasSubTree(pRoot1->left, pRoot2) || HasSubTree(pRoot1->right, pRoot2);
}
//調(diào)用函數(shù)，判斷以這兩個(gè)節(jié)點(diǎn)為根節(jié)點(diǎn)的樹(shù)是否是包含關(guān)系墙歪，1包含2
bool IsSametree(TreeNode* pRoot1, TreeNode* pRoot2)
{
//注意這里要先判斷2是不是空听系，因?yàn)?是空可以直接返回true
if (!pRoot2) return true;
//如果2不空，1是空的虹菲，那1肯定不包含2靠胜，返回false
if (!pRoot1) return false;
//兩個(gè)節(jié)點(diǎn)都有值，但節(jié)點(diǎn)值不同毕源，那肯定也不是包含關(guān)系
if (pRoot1->val != pRoot2->val)
return false;
//如果值相同浪漠，則判斷他們的左右節(jié)點(diǎn)是否也是包含關(guān)系（必須都是包含關(guān)系才行）
else
return IsSametree(pRoot1->left,pRoot2->left) && IsSametree(pRoot1->right,pRoot2->right);
}
兩道題結(jié)題思路是一致的，只是在判斷條件上有差別霎褐，只要搞清楚了子樹(shù)和子結(jié)構(gòu)的區(qū)別址愿，就能很清晰地知道怎么解題了。
