【剑指 offer】树的子结构

描述：

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

假如给定A为{8,8,7,9,2,#,#,#,#,4,7}，B为{8,9,2}，2个树的结构如下，可以看出B是A的子结构

思路：

public class Solution {
    private boolean JudgeLocContain(TreeNode root1, TreeNode root2) {
        //JudgeLocContain方法为‘当前位置包含判断’
        //用于比较 ‘A树root1位置的子树’ 是否包含 B树
        //且只将B树与‘包括root1节点的 靠上部分的树’进行比较，判断是否包含
        if (root1 == null && root2 == null) {
            return true;
            //root1和root2同时遍历，刚好一起比较完毕，说明root1和root2相同，返回true
        }
        if (root1 != null && root2 == null) {
            return true;
            /*此处root2为空代表B树已递归完毕，A树还未完毕，B树与A树之前的结构相同
            题中“约定空树不是任意一个树的子结构” 针对 B树这个整体
            但该方法是对 A树当前位置子树 和 B树 “逐个节点”校验，而判断是否包含
            所以只需要在主方法开始阶段判断B树是否为空即可，此处不必考虑空树约定*/
        }
        if (root1 == null && root2 != null) {
            return false;
        } //root1已完毕，root2还未完毕，说明两者不同

        //此处隐含的剩下一种情况就是两者都还未完毕(两者都不为空,即可以比较两者值)
        if (root1.val != root2.val) {
            return false;
        }//排除两者值不相等的情况，取相等情况返回递归，保证了之前访问的节点相同
        return JudgeLocContain(root1.left, root2.left) &&
               JudgeLocContain(root1.right, root2.right);
    }

    public boolean HasSubtree(TreeNode root1, TreeNode root2) {
        if (root2 == null) { //按照约定，判断B树整体是否为空
            return false;
        }
        if (root1 == null) {//root1为空，肯定不包含root2
            return false;
        }
        /*隐含的情况是root1和root2都不为空
        进行当前位置包含判断JudgeLocContain，并递归左右子树*/
        return JudgeLocContain(root1, root2) || HasSubtree(root1.left, root2) ||
               HasSubtree(root1.right, root2);
    }
}