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

题目：输入两棵二叉树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一样的结构。