題目：二叉樹的結(jié)點定義如下：
struct TreeNode
{
int m_nValue;
TreeNode* m_pLeft;
TreeNode* m_pRight;
};
輸入兩棵二叉樹A和B，判斷樹B是不是A的子結(jié)構(gòu)。
例如，下圖中的兩棵樹A和B，由于A中有一部分子樹的結(jié)構(gòu)和B是一樣的，因此B就是A的子結(jié)構(gòu)。
1 8
/ \ / \
8 7 9 2
/ \
9 2
/ \
4 7
分析：這是2010年微軟校園招聘時的一道題目。二叉樹一直是微軟面試題中經(jīng)常出現(xiàn)的數(shù)據(jù)結(jié)構(gòu)。對微軟有興趣的讀者一定要重點關(guān)注二叉樹。
回到這個題目的本身。要查找樹A中是否存在和樹B結(jié)構(gòu)一樣的子樹，我們可以分為兩步：第一步在樹A中找到和B的根結(jié)點的值一樣的結(jié)點N，第二步再判斷樹A中以N為根結(jié)點的子樹是不是包括和樹B一樣的結(jié)構(gòu)。
第一步在樹A中查找與根結(jié)點的值一樣的結(jié)點。這實際上就是樹的遍歷。對二叉樹這種數(shù)據(jù)結(jié)構(gòu)熟悉的讀者自然知道我們可以用遞歸的方法去遍歷，也可以用循環(huán)的方法去遍歷。由于遞歸的代碼實現(xiàn)比較簡潔，面試時如果沒有特別要求，我們通常都會采用遞歸的方式。下面是參考代碼：
bool HasSubtree(TreeNode* pTreeHead1, TreeNode* pTreeHead2)
{
if((pTreeHead1 == NULL && pTreeHead2 != NULL) ||
(pTreeHead1 != NULL && pTreeHead2 == NULL))
return false;
if(pTreeHead1 == NULL && pTreeHead2 == NULL)
return true;
return HasSubtreeCore(pTreeHead1, pTreeHead2);
}
bool HasSubtreeCore(TreeNode* pTreeHead1, TreeNode* pTreeHead2)
{
bool result = false;
if(pTreeHead1->m_nValue == pTreeHead2->m_nValue)
{
result = DoesTree1HaveAllNodesOfTree2(pTreeHead1, pTreeHead2);
}
if(!result && pTreeHead1->m_pLeft != NULL)
result = HasSubtreeCore(pTreeHead1->m_pLeft, pTreeHead2);
if(!result && pTreeHead1->m_pRight != NULL)
result = HasSubtreeCore(pTreeHead1->m_pRight, pTreeHead2);
return result;
}
在上述代碼中，我們遞歸調(diào)用hasSubtreeCore遍歷二叉樹A。如果發(fā)現(xiàn)某一結(jié)點的值和樹B的頭結(jié)點的值相同，則調(diào)用DoesTree1HaveAllNodeOfTree2，做第二步判斷。
在面試的時候，我們一定要注意邊界條件的檢查，即檢查空指針。當(dāng)樹A或樹B為空的時候，定義相應(yīng)的輸出。如果沒有檢查并做相應(yīng)的處理，程序非常容易崩潰，這是面試時非常忌諱的事情。由于沒有必要在每一次遞歸中做邊界檢查（每一次遞歸都做檢查，增加了不必要的時間開銷），上述代碼只在HasSubtree中作了邊界檢查后，在HasSubtreeCore中作遞歸遍歷。
接下來考慮第二步，判斷以樹A中以N為根結(jié)點的子樹是不是和樹B具有相同的結(jié)構(gòu)。同樣，我們也可以用遞歸的思路來考慮：如果結(jié)點N的值和樹B的根結(jié)點不相同，則以N為根結(jié)點的子樹和樹B肯定不具有相同的結(jié)點；如果他們的值相同，則遞歸地判斷他們的各自的左右結(jié)點的值是不是相同。遞歸的終止條件是我們到達了樹A或者樹B的葉結(jié)點。參考代碼如下：
bool DoesTree1HaveAllNodesOfTree2(TreeNode* pTreeHead1, TreeNode* pTreeHead2)
{
if(pTreeHead2 == NULL)
return true;
if(pTreeHead1 == NULL)
return false;
if(pTreeHead1->m_nValue != pTreeHead2->m_nValue)
return false;
return DoesTree1HaveAllNodesOfTree2(pTreeHead1->m_pLeft, pTreeHead2->m_pLeft) &&
DoesTree1HaveAllNodesOfTree2(pTreeHead1->m_pRight, pTreeHead2->m_pRight);
}
博主何海濤對本博客文章享有版權(quán)。網(wǎng)絡(luò)轉(zhuǎn)載請注明出處http://zhedahht.blog.163.com/。