题目：输入两棵二叉树A和B，判断B是不是A的子结构。
二叉树结点的定义如下：
struct BinaryTreeNode { int m_nValue; BinaryTreeNode *m_pLeft; BinaryTreeNode *m_pRight; };
例如图中的两棵二叉树，由于A中有一部分子树的结构和B是一样的，因此B是A的子结构。
要查找树A中是否存在和树B结构一样的子树，可以分成两步：
- 第一步在树A中找到和B的根节点的值一样的结点R；
- 第二步再判断树A中以R为根结点的子树是不是包含和树B一样的结构。
第一步在树A中查找与根结点的值一样的结点，这实际上就是树的遍历。递归调用HasSubTree遍历二叉树A。如果发现某一结点的值和树B的头结点的值相同，则调用DoesTreeHavaTree2，做第二步判断。
第二步是判断树A中以R为根结点的子树是不是和树B具有相同的结构。
核心代码：
1 bool HasSubtree(BinaryTreeNode* pRoot1, BinaryTreeNode* pRoot2) 2 { 3 bool result = false; 4 5 if(pRoot1 != NULL && pRoot2 != NULL) 6 { 7 if(pRoot1->m_nValue == pRoot2->m_nValue) 8 result = DoesTree1HaveTree2(pRoot1, pRoot2); 9 if(!result) 10 result = HasSubtree(pRoot1->m_pLeft, pRoot2); 11 if(!result) 12 result = HasSubtree(pRoot1->m_pRight, pRoot2); 13 } 14 15 return result; 16 } 17 18 bool DoesTree1HaveTree2(BinaryTreeNode* pRoot1, BinaryTreeNode* pRoot2) 19 { 20 if(pRoot2 == NULL) 21 return true; 22 23 if(pRoot1 == NULL) 24 return false; 25 26 if(pRoot1->m_nValue != pRoot2->m_nValue) 27 return false; 28 29 return DoesTree1HaveTree2(pRoot1->m_pLeft, pRoot2->m_pLeft) && 30 DoesTree1HaveTree2(pRoot1->m_pRight, pRoot2->m_pRight); 31 }
注意在使用指针的时候一定要注意边界条件，即检查空指针。当树A或树B为空的时候，定义相应的输出。如果没有检查并做相应的处理，程序非常容易崩溃。
微信公众号： 猿人谷
如果您认为阅读这篇博客让您有些收获，不妨点击一下右下角的【推荐】
如果您希望与我交流互动，欢迎关注微信公众号
本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接。
