【剑指offer】面试题18：输入两颗二叉树A和B,判断B是不是A的子结构？

二叉树的定义：

struct BinaryTreeNode { int m_nValue; BinaryTreeNode* m_pLeft; BinaryTreeNode* m_PRight; };

思路： 1.遍历两个二叉树，分别判断其的根节点，左右孩子的值是否相等 2.若根节点值相等，但其左右孩子值不相等，我们需要条跳到根节点上重新进行判断 //递归来说思路比较清晰，我们用递归来解决这个问题

bool HasSubtree(BinaryTreeNode * pRoot1, BinaryTreeNode* pRoot2) { bool result = false; if (pRoot1 != NULL &&pRoot2 != NULL) { if (pRoot1->m_nValue == pRoot2->m_nValue) { result = DoesTree1HaveTree2(pRoot1, pRoot2); } if (!result) { result = HasSubtree(pRoot1->m_pLeft, pRoot2); } if (!result) { result = HasSubtree(pRoot1->m_pRight, pRoot2); } } return result; } //判断树1是否有树2 //递归函数肯定要有出口 bool DoesTree1HaveTree2(BinaryTreeNode* pRoot1, BinaryTreeNode* pRoot2) { if (pRoot1 == NULL) { return false; } if (pRoot2 == NULL) { return true; } if (pRoot1->m_nValue != pRoot2->m_nValue) { return false; } return DoesTree1HaveTree2(pRoot1->m_pLeft, pRoot2->m_pLeft) && DoesTree1HaveTree2(pRoot1-> m_pRight, pRoot2->m_pRight);//判断左右子树是否相等 }