剑指offer026输入两棵二叉树A,B,判断B是不是A的子结构

Problem:

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

Intuition:

树和链表都是典型的递归结构，遇到题目优先尝试从递归的角度来考虑。这个题目我们要找树A与B是否存在子结构的关系，那么这个过程可以分为两步。第一步，在树A中找到和树B的根节点一样的节点R;第二步，判断树A中以R为根节点的子树是不是包含和树B一样的结构。

Solution:

public class CodingInterview_026 {

    class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int val){
            this.val=val;
        }
    }
    public boolean HasSubtree(TreeNode root1, TreeNode root2) {
        if (root1 == null || root2 == null)
            return false;
        return isSubtreeWithRoot(root1, root2) || HasSubtree(root1.left, root2) || HasSubtree(root1.right, root2);
    }

    private boolean isSubtreeWithRoot(TreeNode root1, TreeNode root2) {
        if (root2 == null)
            return true;
        if (root1 == null)
            return false;
        if (root1.val != root2.val)
            return false;
        return isSubtreeWithRoot(root1.left, root2.left) && isSubtreeWithRoot(root1.right, root2.right);
    }
}