题目：输入两棵二叉树A和B，判断B是不是A的子结构。
#include<iostream> using namespace std; struct BinaryTreeNode { double m_dbValue; BinaryTreeNode* m_pLeft; BinaryTreeNode* m_pRight; }; bool DoesTree1HasTree2(BinaryTreeNode* pRoot1, BinaryTreeNode* pRoot2); bool Equal(double num1, double num2); //1.在树1中找到一个与树2根节点相同的节点 bool HasSubtree(BinaryTreeNode* pRoot1, BinaryTreeNode* pRoot2) { //一个树或两个树为空 均返回false bool res = false; if (pRoot1 != nullptr && pRoot2 != nullptr) { if (Equal(pRoot1->m_dbValue, pRoot2->m_dbValue)) { res = DoesTree1HasTree2(pRoot1, pRoot2); } if (!res) { res = HasSubtree(pRoot1->m_pLeft, pRoot2); } if (!res) { res = HasSubtree(pRoot1->m_pRight, pRoot2); } } return res; } //2.判断树1中的该节点是否有包含树2 bool DoesTree1HasTree2(BinaryTreeNode* pRoot1, BinaryTreeNode* pRoot2) { if (pRoot2 == nullptr) { return true; } if (pRoot1 == nullptr) { return false; } if (!Equal(pRoot1->m_dbValue, pRoot2->m_dbValue)) { return false; } return DoesTree1HasTree2(pRoot1->m_pLeft, pRoot2->m_pLeft) && DoesTree1HasTree2(pRoot1->m_pRight, pRoot2->m_pRight); } bool Equal(double num1, double num2) { if (abs(num1 - num2) < 0.0000001) { return true; } else { return false; } } //================= BinaryTreeNode* CreateBinaryTreeNode(double dbValue) { BinaryTreeNode* pNode = new BinaryTreeNode(); pNode->m_dbValue = dbValue; pNode->m_pLeft = nullptr; pNode->m_pRight = nullptr; return pNode; } void ConnectTreeNodes(BinaryTreeNode* pParent, BinaryTreeNode* pLeft, BinaryTreeNode* pRight) { if (pParent != nullptr) { pParent->m_pLeft = pLeft; pParent->m_pRight = pRight; } } void DestroyTree(BinaryTreeNode* pRoot) { if (pRoot != nullptr) { BinaryTreeNode* pLeft = pRoot->m_pLeft; BinaryTreeNode* pRight = pRoot->m_pRight; delete pRoot; pRoot = nullptr; DestroyTree(pLeft); DestroyTree(pRight); } } int main() { BinaryTreeNode* pNodeA1 = CreateBinaryTreeNode(8); BinaryTreeNode* pNodeA2 = CreateBinaryTreeNode(8); BinaryTreeNode* pNodeA3 = CreateBinaryTreeNode(7); BinaryTreeNode* pNodeA4 = CreateBinaryTreeNode(9); BinaryTreeNode* pNodeA5 = CreateBinaryTreeNode(2); BinaryTreeNode* pNodeA6 = CreateBinaryTreeNode(4); BinaryTreeNode* pNodeA7 = CreateBinaryTreeNode(7); ConnectTreeNodes(pNodeA1, pNodeA2, pNodeA3); ConnectTreeNodes(pNodeA2, pNodeA4, pNodeA5); ConnectTreeNodes(pNodeA5, pNodeA6, pNodeA7); BinaryTreeNode* pNodeB1 = CreateBinaryTreeNode(8); BinaryTreeNode* pNodeB2 = CreateBinaryTreeNode(9); BinaryTreeNode* pNodeB3 = CreateBinaryTreeNode(2); ConnectTreeNodes(pNodeB1, pNodeB2, pNodeB3); //bool res = HasSubtree(pNodeA1, pNodeB1); bool res = HasSubtree(nullptr, nullptr); return 0; }
