Question

题目：输入两棵二叉树A和B，判断B是不是A的子结构。二叉树结点的定义如下：

例如图3.9中的两棵二叉树，由于A中有一部分子树的结构和B是一样的，因此B是A的子结构。

图3.9　两棵二叉树A和B，右边的树B是左边的树A的子结构

和链表相比，树中的指针操作更多也更复杂，因此与树相关的问题通常会比链表的要难。如果想加大面试的难度，树的题目是很多面试官的选择。面对着大量的指针操作，我们要更加小心，否则一不留神就会在代码中留下隐患。

现在回到这个题目本身。要查找树A中是否存在和树B结构一样的子树，我们可以分成两步：第一步在树A中找到和B的根结点的值一样的结点R，第二步再判断树A中以R为根结点的子树是不是包含和树B一样的结构。

以上面的两棵树为例来详细分析这个过程。首先我们试着在树A中找到值为8（树B的根结点的值）的结点。从树A的根结点开始遍历，我们发现它的根结点的值就是8。接着我们就去判断树A的根结点下面的子树是不是含有和树B一样的结构（如图3.10所示）。在树A中，根结点的左子结点的值是8，而树B的根结点的左子结点是9，对应的两个结点不同。

图3.10　树A的根结点和B的根结点的值相同，但树A的根结点下面（实线部分）的结构和树B的结构不一致

因此我们仍然需要遍历树A，接着查找值为8的结点。我们在树的第二层中找到了一个值为8的结点，然后进行第二步判断，即判断这个结点下面的子树是否含有和树B一样结构的子树（如图3.11所示）。于是我们遍历这个结点下面的子树，先后得到两个子结点9和2，这和树B的结构完全相同。此时我们在树A中找到了一个和树B的结构一样的子树，因此树B是树A的子结构。

图3.11　在树A中找到第二个值为8的结点，该结点下面（实线部分）的结构和B的结构一致

第一步在树A中查找与根结点的值一样的结点，这实际上就是树的遍历。对二叉树这种数据结构熟悉的读者自然知道可以用递归的方法去遍历，也可以用循环的方法去遍历。由于递归的代码实现比较简洁，面试时如果没有特别要求，我们通常都会采用递归的方式。下面是参考代码：

在面试的时候，我们一定要注意边界条件的检查，即检查空指针。当树A或树B为空的时候，定义相应的输出。如果没有检查并做相应的处理，程序非常容易崩溃，这是面试时非常忌讳的事情。

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

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

我们注意到上述代码有多处判断一个指针是不是NULL，这样做是为了避免试图访问空指针而造成程序崩溃，同时也设置了递归调用的退出条件。在写遍历树的代码的时候一定要高度警惕，在每一处需要访问地址的时候都要问自己这个地址有没有可能是NULL，如果是NULL该怎么处理。

面试小提示：

二叉树相关的代码有大量的指针操作，每一次使用指针的时候，我们都要问自己这个指针有没有可能是NULL，如果是NULL该怎么处理。

为了确保自己的代码完整正确，在写出代码之后应聘者至少要用几个测试用例来检验自己的程序：树A和树B的头结点有一个或者两个都是空指针，在树A和树B中所有结点都只有左子结点或者右子结点，树A和树B的结点中含有分叉。只有这样才能写出让面试官满意的鲁棒代码。

源代码：

本题完整的源代码详见18_SubstructureInTree项目。

测试用例：

- 功能测试（树A和树B都是普通的二叉树，树B是或者不是树A的子结构）。

- 特殊输入测试（两棵二叉树的一个或者两个根结点为NULL指针、二叉树的所有结点都没有左子树或者右子树）。

本题考点：

- 考查对二叉树遍历算法的理解及递归编程能力。

- 考查代码的鲁棒性。本题的代码中含有大量的指针操作，稍有不慎程序就会崩溃。应聘者需要采用防御性编程的方式，每次访问指针地址之前都要考虑这个指针有没有可能是NULL。