26-树的子结构

输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)

B是A的子结构， 即 A中有出现和B相同的结构和节点值。

例如: 给定的树 A:

给定的树 B：

返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。

涉及到二叉树的题目，往往是通过递归来缩小问题规模，通过解决子树的问题来解决整个问题。

假如B是A的子结构，那么B的左子树肯定是A的子结构，右子树也肯定是A的子结构，这里需要注意一点，就是递归判断子树时要保证是在同一个父节点下。

public boolean isSubStructure(TreeNode A, TreeNode B) {
        if (B == null || A == null) { //首先将B为空的情况排除掉，因为后面递归时假如B为空了，是表示比较完了，是子树。
            return false;
        }
        if(!isSubStructureCore(A,B)){//如果B是以A为根节点的子结构，这里注意，是以A为根节点。
            return isSubStructure(A.left, B) || isSubStructure(A.right, B); //如果不是，那么就递归的查看是不是以A.left或A.right为根节点的子树 
        }
        return true;//如果是，就直接返回true
    }
		//判断是否是B是以A为根节点的子结构
    private boolean isSubStructureCore(TreeNode A,TreeNode B) {
        if (B == null) { //B已经比较完所有节点了，那么说明前面的都匹配，是子树无疑了。
            return true;
        }
        if (A == null) {//如果B不为空，但A为空，说明肯定不是子树了。
            return false;
        }
        if (A.val == B.val) { //如果节点相等，则需要继续比较左右子树
            return isSubStructureCore(A.left, B.left) && isSubStructureCore(A.right, B.right);
        }
        return false;
    }

上面代码可以进一步简化。

public boolean isSubStructure(TreeNode A, TreeNode B) {
        if (B == null || A == null) {
            return false;
        }
        //三个条件分别是 B是以A为根节点的子树？ 以A.left为根节点的子树里包含B结构？以A.right为根节点的子树里包含B结构？
        return isSubStructureCore(A,B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
       
    }

    private boolean isSubStructureCore(TreeNode A,TreeNode B) {
        if (B == null) {
            return true;
        }
        if (A == null) {
            return false;
        }
        //如果节点值不相同，那么没必要比下去了。如果节点值相同，则继续比
         return A.val == B.val && isSubStructureCore(A.left, B.left) && isSubStructureCore(A.right, B.right);
    }

这里要注意上面两个方法的不同点：

• isSubStructure(TreeNode A, TreeNode B)： 以A为根节点的树里是否存在B结构
• isSubStructureCore(TreeNode A,TreeNode B)： 以A为根节点的树是不是与B是相同的结构

isSubStructure:
      4           2
     / \
    2   1
isSubStructureCore:
      4           4
     / \         / \
    2   1       2   1