树的子结构

题目描述：

输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

分析：

首先，B=null,则返回false
如果B是A的子树，那么A中必然含有和B一模一样的子树

数的子结构示例
要找到A当中是否含有和B一样的结构的子树，那么可以分为两步走：
一、在A中找到和B的根节点值一样的节点R；
二、判断R节点下是否有和B一样结构的子树；
这是一个递归的过程。

递归的使用可以一下三步来完成求解过程：
　　1. 递归截止条件。
　　递归的截止条件是为了递归能够避免无限循环下去，首先来分析什么情况下递归截止返回遍历结果。
(1) 根据题目要求，如果B数是个空树，递归截止。
(2) 如果被遍历的树A是空树，自然而然递归截止。
(3) 如果比较的是B的尾节点，无法进行下去，递归也会截止。
(4) 如果A树从头遍历到尾始终没有和B的节点相同的节点，递归截止。
　　2. 递归的前后衔接。
　　如果A的根节点值以及左右子节点情况和B的根节点完全相同，那么A和B都继续滑动到他们的左右子节点进行比较；如果A的根节点值和B的根节点值是相同的，但是左右子节点的情况是不相同的，那么只滑动A到他的左右子节点再与B比较。如果A的根节点的值和B的根节点的值不相同，那么A直接滑动到他的左右自己点再和B的根节点比较，直到遍历完成。
　　3. 递归节点数据的处理。
　　根据题目，本题目中用到的递归并没有数据处理，只是比较判断两个树节点是否相同。对于其他递归，可以具体情况具体对待。

代码：

/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
       if(root2 == null || root1 == null)
            return false;
       boolean result = false;
        //A上的节点R和B的根节点相同，则判断下面的结构是否相同。
       if(root1.val == root2.val)
           result = isSubTree(root1,root2);
       //如果上一步判断的结果是false，那么，将A往下遍历比较，先比较A的左子树中有没有和B相同的子结构
       if(result == false)
           result = HasSubtree(root1.left,root2);
        //再比较A的右子树中有没有和B相同的子结构
       if(result == false)
           result = HasSubtree(root1.right,root2);
        //递归遍历完了
       return result;
    }
    
    //如果已经有节点R和B的根节点相同，那么用这个方法来判断R的子树和B的结构是否一致
    private boolean isSubTree(TreeNode root1,TreeNode root2){
        if(root2 == null)
            return true;
        if(root1 == null)
            return false;
        if(root2.val != root1.val)
            return false;
        return isSubTree(root1.left,root2.left)&&isSubTree(root1.right,root2.right);
    }
}

后来看到大神的j简洁写法如下：

/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
       if(root2 == null || root1 == null)
            return false;
       return isSubTree(root1,root2) || HasSubtree(root1.left,root2) || HasSubtree(root1.right,root2);
    }
    
    //如果已经有节点R和B的根节点相同，那么用这个方法来判断R的子树和B的结构是否一致
    private boolean isSubTree(TreeNode root1,TreeNode root2){
        if(root2 == null)
            return true;
        if(root1 == null)
            return false;
        if(root2.val != root1.val)
            return false;
        return isSubTree(root1.left,root2.left)&&isSubTree(root1.right,root2.right);
    }
}

运行结果