[剑指offer][Java]树的子结构

题目

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

程序核心思想

这个题目表述的不太清楚，它的意思是说，如果B树是空树，那么它不是任何树的子树，除此之外，只要在A树中，有跟B树结构相同的一部分，那么B树就是它的子树。
看到题目，首先想到递归：如果两个结点的值相同，那么检查它们的左右孩子的值是否相同，如此递归下去，如果相同，则返回true，这是毋庸置疑的，但是如果不同，则返回false吗？不是这样的，想一下，这只能说明，B树跟以A树的那个结点为根节点的结构不相同，这难道就表明A树里不含有跟B树相同的结构了吗？答案显而易见不是这样，所以就需要找A树的下一个结点（它的左孩子和右孩子），看以它为根节点是不是有跟B树有同样的结构。
只有找遍了A树的所有结点，都没有跟B树相同的结构，才能说B树不是A树的子树。

Tips

• 两个递归，一个递归A树的根节点，一个递归结构（比较A树B树的结点值是否相等）。

代码

/**
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(root1 == null || root2 == null)    return false;
        
        if(Has(root1, root2) == false){
            return HasSubtree(root1.left, root2) || HasSubtree(root1.right, root2);
        }else{
            return true;
        }
    }
    
    public boolean Has(TreeNode root1,TreeNode root2) {
        if(root2 == null){
            return true;
        }else if(root1 != null){
            return root1.val == root2.val && Has(root1.left, root2.left) && Has(root1.right, root2.right);
        }else{
            return false;
        }
    }
}