面试题18：树的子结构

掌握这题的思路：

第一步在树A中找到和B的根节点的值一样的节点R，第二步在判断树A中以R为根节点的子树是不是包含和树B一样的结构

 1 bool HasSubtreeCore(BinaryTreeNode* pRoot1, BinaryTreeNode* pRoot2);
 2 bool DoesTree1HaveTree2(BinaryTreeNode* pRoot1, BinaryTreeNode* pRoot2);
 3 
 4 bool HasSubtree(BinaryTreeNode* pRoot1, BinaryTreeNode* pRoot2)
 5 {
 6     bool result = false;
 7 
 8     if(pRoot1 != NULL && pRoot2 != NULL)
 9     {
10         if(pRoot1->m_nValue == pRoot2->m_nValue)
11             result = DoesTree1HaveTree2(pRoot1, pRoot2);
12         if(!result)
13             result = HasSubtree(pRoot1->m_pLeft, pRoot2);
14         if(!result)
15             result = HasSubtree(pRoot1->m_pRight, pRoot2);
16     }
17 
18     return result;
19 }
20 
21 bool DoesTree1HaveTree2(BinaryTreeNode* pRoot1, BinaryTreeNode* pRoot2)
22 {
23     if(pRoot2 == NULL)    //注意判断和树2相同的条件是把树2都遍历完
24         return true;
25 
26     if(pRoot1 == NULL)
27         return false;
28 
29     if(pRoot1->m_nValue != pRoot2->m_nValue)    //这里用!=要是用==就变得复杂了
30         return false;
31 
32     return DoesTree1HaveTree2(pRoot1->m_pLeft, pRoot2->m_pLeft) &&
33         DoesTree1HaveTree2(pRoot1->m_pRight, pRoot2->m_pRight);
34 }