输入2棵二叉树A和B,判断B是不是A的子结构。
1 struct BinaryTreeNode //节点 2 { 3 int m_nValue; 4 BinaryTreeNode* m_pLeft; 5 BinaryTreeNode* m_pRight; 6 };
1 bool DoseTree1HaveTree2(BinaryTreeNode* pRoot1 ,BinaryTreeNode* pRoot2) 2 { 3 4 if (pRoot2 == NULL) 5 { 6 return true ; 7 } 8 if (pRoot1 == NULL) 9 { 10 return false ; 11 } 12 if (pRoot1->m_nValue != pRoot2->m_nValue) 13 { 14 return false ; 15 } 16 17 return DoseTree1HaveTree2(pRoot1->m_pLeft , pRoot2->m_pLeft) && DoseTree1HaveTree2(pRoot1->m_pRight ,pRoot2->m_pRight) ; 18 } 19 bool HasSubtree(BinaryTreeNode* pRoot1 ,BinaryTreeNode* pRoot2) 20 { 21 bool result = false ; 22 if (pRoot1 && pRoot2) 23 { 24 if (pRoot1->m_nValue == pRoot2->m_nValue) 25 { 26 result = DoseTree1HaveTree2(pRoot1 , pRoot2); 27 } 28 if (!result) 29 { 30 result = HasSubtree(pRoot1->m_pLeft , pRoot2); 31 } 32 if (!result) 33 { 34 result = HasSubtree(pRoot1->m_pRight , pRoot2); 35 } 36 } 37 38 return result ; 39 }
原文:http://www.cnblogs.com/csxcode/p/3695102.html