题目：输入两棵二叉树A和B，判断B是不是A的子结构。
/// <summary>
/// 遍历树判断
/// </summary>
/// <param name="A"></param>
/// <param name="B"></param>
/// <returns></returns>
public bool IsSubStructure(TreeNode A, TreeNode B)
{
var result = false;
if (A != null && B != null)
{
if (A.val == B.val)
{
result = DoesTree1HaveTree2(A, B);
}
if (!result)
result = IsSubStructure(A.left, B);
if (!result)
result = IsSubStructure(A.right, B);
}
return result;
}
/// <summary>
/// 找到想等根节点后，判断是否是子树
/// </summary>
/// <param name="A"></param>
/// <param name="B"></param>
/// <returns></returns>
public bool DoesTree1HaveTree2(TreeNode A, TreeNode B)
{
if (B == null) return true;
if (A == null) return false;
if (A.val != B.val) return false;
return DoesTree1HaveTree2(A.left, B.left) && DoesTree1HaveTree2(A.right, B.right);
}
public class TreeNode
{
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x)
{
val = x;
}
}
第一步在树A中找到和B的根结点的值一样的结点R，第二步再判断树A中以R为根结点的子树是不是包含和树B一样的结构。
