面試題18：樹的子結(jié)構(gòu)
題目：輸入兩棵二叉樹A和B，判斷B是不是A的子結(jié)構(gòu)。二叉樹結(jié)點(diǎn)的定義如下：

struct BinaryTreeNode {int value;BinaryTreeNode *lchild;BinaryTreeNode *rchild; };

代碼如下:

bool HasSubtree(BinaryTreeNode *pRoot1, BinaryTreeNode *pRoot2) {bool res = false;if (pRoot1 != nullptr && pRoot2 != nullptr){if (pRoot1->value == pRoot2->value) res = DoesTree1HaveTree2(pRoot1, pRoot2);if (!res) res = HasSubtree(pRoot1->lchild, pRoot2);if (!res) res = HasSubtree(pRoot1->rchild, pRoot2);}return res; }bool DoesTree1HaveTree2(BinaryTreeNode *pRoot1, BinaryTreeNode *pRoot2) {if (pRoot2 == nullptr) return true;if (pRoot1 == nullptr) return true;if (pRoot1->value != pRoot2->value) return false;return DoesTree1HaveTree2(pRoot1->lchild, pRoot2->lchild) && DoesTree1HaveTree2(pRoot1->rchild, pRoot2->rchild); }

面試小提示：
二叉樹相關(guān)的代碼有大量的指針操作，每一次使用指針的時(shí)候，我們都要問自己這個(gè)指針有沒有可能是NULL，如果是NULL該怎么處理。

為了確保自己的代碼完整正確，在寫出代碼之后應(yīng)聘者至少要用幾個(gè)測試用例來檢驗(yàn)自己的程序：

樹A和樹B的頭結(jié)點(diǎn)有一個(gè)或者兩個(gè)都是空指針

在樹A和樹B中所有結(jié)點(diǎn)都只有左子結(jié)點(diǎn)或者右子結(jié)點(diǎn)

樹A和樹B的結(jié)點(diǎn)中含有分叉

只有這樣才能寫出讓面試官滿意的魯棒代碼。

● 功能測試（樹A和樹B都是普通的二叉樹，樹B是或者不是樹A的子結(jié)構(gòu)）。
● 特殊輸入測試（兩棵二叉樹的一個(gè)或者兩個(gè)根結(jié)點(diǎn)為NULL指針、二叉樹的所有結(jié)點(diǎn)都沒有左子樹或者右子樹）。
本題考點(diǎn)：
● 考查對二叉樹遍歷算法的理解及遞歸編程能力。
● 考查代碼的魯棒性。本題的代碼中含有大量的指針操作，稍有不慎程序就會崩潰。應(yīng)聘者需要采用防御性編程的方式，每次訪問指針地址之前都要考慮這個(gè)指針有沒有可能是NULL。

總結(jié)

以上是生活随笔為你收集整理的[剑指offer]面试题18：树的子结构的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。