程序员面试题精选100题（50）-树的子结构[数据结构]

return result;

}

在上述代码中，我们递归调用hasSubtreeCore遍历二叉树A。如果发现某一结点的值和树B的头结点的值相同，则调用DoesTree1HaveAllNodeOfTree2，做第二步判断。

在面试的时候，我们一定要注意边界条件的检查，即检查空指针。当树A或树B为空的时候，定义相应的输出。如果没有检查并做相应的处理，程序非常容易崩溃，这是面试时非常忌讳的事情。由于没有必要在每一次递归中做边界检查（每一次递归都做检查，增加了不必要的时间开销），上述代码只在HasSubtree中作了边界检查后，在HasSubtreeCore中作递归遍历。

接下来考虑第二步，判断以树A中以N为根结点的子树是不是和树B具有相同的结构。同样，我们也可以用递归的思路来考虑：如果结点N的值和树B的根结点不相同，则以N为根结点的子树和树B肯定不具有相同的结点；如果他们的值相同，则递归地判断他们的各自的左右结点的值是不是相同。递归的终止条件是我们到达了树A或者树B的叶结点。参考代码如下：

bool DoesTree1HaveAllNodesOfTree2(TreeNode* pTreeHead1, TreeNode* pTreeHead2)

{

        if(pTreeHead2 == NULL)

                return true;

 

        if(pTreeHead1 == NULL)

                return false;

 

        if(pTreeHead1->m_nValue != pTreeHead2->m_nValue)

                return false;