27_树的子结构

要求：输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
思路:
参考
第一步，在树A中找到和树B的根节点的值一样的结点R；使用递归去先序遍历A的每个节点。
HasSubtree函数：
1、特例处理： 当 树 A 为空 或 树 B 为空 时，直接返回 false ；
2、返回值： 若树 B 是树 A 的子结构，则必满足以下三种情况之一，因此用或 || 连接；
  1.以 节点 A 为根节点的子树 包含树 B ，对应 DoesTree1HaveTree2(A, B)；
  2.树 B 是 树 A 左子树 的子结构，对应 HasSubtree(A.left, B)；
  3.树 B 是 树 A 右子树 的子结构，对应 HasSubtree(A.right, B)；
以上 2. 3. 实质上是在对树 A 做 先序遍历 。

第二步，判断树A中以R为根节点的子树是不是包含和树B一样的结构。使用递归去比较A每个节点对应的B每个节点值是否相同。
DoesTree1HaveTree2函数：
1、终止条件：
  1.当节点 B为空：说明树 BB 已匹配完成（越过叶子节点），因此返回 true ；
  2.当节点 A为空：说明已经越过树 AA 叶子节点，即匹配失败，返回 false ；
  3.当节点 A 和 B 的值不同：说明匹配失败，返回 false ；
2、返回值：
  1.判断 A 和 B 的左子节点是否相等，即 DoesTree1HaveTree2(A.left, B.left) ；
  2.判断 A 和 B 的右子节点是否相等，即 DoesTree1HaveTree2(A.right, B.right) ；

public class L27_HasSubtree {
// 简化代码
//    public boolean isSubStructure(TreeNode A, TreeNode B) {
//        return (A != null && B != null) && (recur(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B));
//    }
//    boolean recur(TreeNode A, TreeNode B) {
//        if(B == null) return true;
//        if(A == null || A.val != B.val) return false;
//        return recur(A.left, B.left) && recur(A.right, B.right);
//    }
    // 主代码
    public boolean HasSubtree(TreeNode0 A, TreeNode0 B){
        boolean result = false;
        if(A!=null && B!=null){
            // 先序遍历==> 根-左-右
            if(A.value == B.value){
                // 如果节点值相等，则去判断A中以R为根节点的子树是否包含和树B一样的结构
                result = DoesTree1HaveTree2(A,B);
            }
            //如果以上未找到相同B树，则遍历A左子树
            if(!result){
                // 遍历每个A左子树
                result=HasSubtree(A.left,B);
            }
            // 说明A左子树未找到相同的B树,则遍历A右子树
            if(!result){
                result=HasSubtree(A.right,B);
            }
        }
        return result;

    }
// 判断树A中以R为根节点的子树是不是包含和树B一样的结构
    public boolean DoesTree1HaveTree2(TreeNode0 A, TreeNode0 B){
        if(B==null){
            return true;
        }
        if(A==null){
            return false;
        }
        
        if(A.value!=B.value){
            return false;
        }
        // 能进行下一步，说明A的值等于B的值
        return DoesTree1HaveTree2(A.left,B.left)&&DoesTree1HaveTree2(A.right,B.right);
    }
}