《剑指offer》 第26题 树的子结构

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

首先要正确理解子结构。子树是所有节点都相同，而子结构仅要求部分相同。

这里的892组成的树是左边树的子结构，但不是子树
这里有三种情况，两树完全相同，B在A的左子树上，B在A的右子树上。因此需要比较B的根节点和A的根节点，左右子节点相比，这3类情况。

public class Solution {
    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
        boolean result = false;
        //先判断根不为空，否则直接返回默认值false
        if(root1!=null && root2!=null){
        //根不为空，且两个根的值相同，需要继续比较，此时调用比较方法 直接跳到HasTree
            if(root1.val == root2.val){
                result = HasTree(root1,root2);
            }
        //由于A树比较大，所以根节点不同时，应该拿A树的左右节点去和B树根比较
            if(!result)
                result = HasTree(root1.left,root2);
            if(!result){
                result = HasTree(root1.right,root2);   
            }
        }       
        return result;
    }

   public boolean HasTree(TreeNode root1,TreeNode root2){
        //首先是递归结束条件，递归到B没有子节点时，说明比较完了，B是A子结构
        //遍历到A没有子节点时，说明还有B的子孙节点没有比较，此时B不是A的结构
        //这两句的顺序不能颠倒，因为先判断的B树是否还有节点。
        if(root2==null) return true; 
        if(root1==null) return false;
        //进行值的比较
        if(root1.val != root2.val) return false;
        //到这里说明传入的两颗树的根节点值相同，进入根的左右子节点的比较，进行递归
       return HasTree(root1.left,root2.left) && HasTree(root1.right,root2.right);
   }
}