剑指Offer面试题18（Java版）：树的子结构

╰半夏微凉° 2022-07-16 04:53 139阅读 0赞

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

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

![Center][]

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

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

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

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

下面我们用Java代码来实现：

**\[java\]**  [view plain][]   [copy][view plain]

1.  /\*\* 
2.   \* 输入两棵二叉树A和B，判断B是不是A 的子结构。 
3.   \*/  
4.  **package** swordForOffer;  
5.    
6.  **import** utils.BinaryTreeNode;  
7.    
8.  /\*\* 
9.   \* @author JInShuangQi 
10.  \* 
11.  \* 2015年8月1日 
12.  \*/  
13. **public** **class** E18SubstructureInTree \{  
14.     **public** **boolean** hasSubTree(BinaryTreeNode root1,BinaryTreeNode root2)\{  
15.         **if**(root2 == **null**)  
16.             **return** **true**;  
17.         **if**(root1 == **null**)  
18.             **return** **false**;  
19.         **boolean** result = **false**;  
20.           
21.         **if**(root1 != **null** && root2 != **null**)\{  
22.             **if**(root1.value == root2.value)  
23.                 result = doesTree1HaveTree2(root1,root2);  
24.             **if**(!result)  
25.                 result = hasSubTree(root1.leftNode,root2);  
26.             **if**(!result)  
27.                 result = hasSubTree(root1.rightNode ,root2);  
28.         \}  
29.         **return** result;  
30.     \}  
31.     **public** **boolean** doesTree1HaveTree2(BinaryTreeNode root1,BinaryTreeNode root2)\{  
32.         **if**(root2 == **null**)  
33.             **return** **true**;  
34.         **if**(root1 == **null**)  
35.             **return** **false**;  
36.         **if**(root1.value != root2.value)  
37.             **return** **false**;  
38.         **return** doesTree1HaveTree2(root1.leftNode,root2.leftNode) && doesTree1HaveTree2(root1.rightNode,root2.rightNode);  
39.     \}  
40. \}

![save_snippets.png][]

我们注意到上述代码有多处判断一个指针是不是NULL，这样做是为了避免试图访问空指针而造成程序的崩溃，在每一处需要访问地址的时候要问自己这个地址有没有可能是NULL，如果是NULl该怎么处理

[Center]: /images/20220716/e7181e1a29ef4d5285c0994d29ebca92.png
[view plain]: http://blog.csdn.net/jsqfengbao/article/details/47191543#
[save_snippets.png]: /images/20220716/4dc4b4dbd7ae44228680f51284433874.png