思路:
先统计B数的非空节点数countB。然后前序遍历A,当遇到A的值和B的第一个值相等时,则进行统计左右结构和值都相等的节点数和sum,如果sum == countB,则true。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int countB = 0;
public boolean flag = false;
public boolean isSubStructure(TreeNode A, TreeNode B) {
if(B == null || A == null) {
return false;
}
count(B);
identify(A, B);
return flag;
}
public void identify(TreeNode A, TreeNode B) {
if (flag || A == null || B == null) {
return;
}
if (A.val == B.val ) {
// 统计结构和值都相等的节点数
int sum = countAB(A.left, B.left) + countAB(A.right, B.right) + 1;
if(sum == countB) {
flag = true;
return;
}
}
identify(A.left, B);
identify(A.right, B);
return;
}
public int countAB(TreeNode A, TreeNode B) {
if (A == null || B == null) {
return 0;
}
if(A.val == B.val) {
return countAB(A.left, B.left) + countAB(A.right, B.right) + 1;
}
return 0;
}
public void count(TreeNode t) {
if (t == null) {
return;
}
countB ++;
count(t.left);
count(t.right);
}
}