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