输入两棵二叉树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
}
}