剑指 Offer 26. 树的子结构

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

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

class Solution {

    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if (A==null || B==null) return  false;
        //前序遍历,首先遍历A(判断B是否为以A为根节点的子树的子结构),遍历左子树 ,遍历右子树。
        return  recur(A,B)||isSubStructure(A.left,B)||isSubStructure(A.right,B);
    }

    boolean recur(TreeNode p, TreeNode q){  //判断q是否为以p为根节点的子树的子结构
        //System.out.println(p.val+" "+q.val);
        if (q==null) return true;          //q遍历完了,是子结构
        if (p==null) return false;         //这里q肯定不为空,p为空,不满足题意。
        if (p.val==q.val)                  // 如果相等,继续递归调用
            return recur(p.left,q.left) && recur(p.right,q.right);
        return false;                       // pq都不为空且不相等,默认返回false
    }
}

 

上一篇:用递归计算1-100所有自然数的和


下一篇:递归模板