【面试题18】树的子结构

【题目描述】

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

【解决方案】

根据图示，用递归解决。

注意代码的鲁棒性，树的操作很可能会访问不存在的内存，必须做好对null的处理!

我的代码示例，仅供参考：

 1         public static bool HasSubTree(BinaryTreeNode treeA, BinaryTreeNode treeB)
 2         {
 3             bool result = false;
 4 
 5             if (treeA != null && treeB != null)
 6             {
 7                 if (treeA.Value == treeB.Value)
 8                 {
 9                     result = DoseTreeAHasTreeB(treeA, treeB);
10                 }
11 
12                 if (!result)
13                 {
14                     result = HasSubTree(treeA.Left, treeB);
15                 }
16 
17                 if (!result)
18                 {
19                     result = HasSubTree(treeA.Right, treeB);
20                 }
21             }
22 
23             return result;
24         }
25 
26         public static bool DoseTreeAHasTreeB(BinaryTreeNode treeA, BinaryTreeNode treeB)
27         {
28             if (treeB == null)
29             {
30                 return true;
31             }
32 
33             if (treeA == null)
34             {
35                 return false;
36             }
37 
38             if (treeA.Value != treeB.Value)
39             {
40                 return false;
41             }
42 
43             return DoseTreeAHasTreeB(treeA.Left, treeB.Left)
44                 && DoseTreeAHasTreeB(treeA.Right, treeB.Right);
45         }