题目

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

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

例如:

给定的树 A:

    3
   / \
  4   5
 / \
1   2

给定的树 B:

 4 
 /
1

返回 true

解答

定义:B是A的真子结构,即B是A的子结构且根节点相等。

例如:

 4        4                4
 /    和   \    都是      / \   的真子结构。
1           2            1   2

如此,这题需要使用双递归函数,一个判断子结构,一个判断真子结构。

判断子结构:

对树A进行进行先序遍历,首先判断当前节点作为根的子树是否含有真子结构B,若不包含,则递归判断A的左子树和右子树是否含有子结构B。

判断真子结构:

注意这里不是要判断A和B要完全相等,只要结构和值都对应上就行,A比B多出来的节点,在B中对应为空。

两棵树同时进行先序遍历,逐个节点判断。在同一个遍历点:

  • A != NULL && B == NULL,合理。返回 true

此处就是与判断两棵树完全相等的区别。

  • A == NULL && B != NULL,说明结构不同了,返回 false

  • A != NULL && B != NULL,当前结构可以对应:

    • A->val != B->val,值对不上,还是不行,返回 false
    • A->val == B->val,当前结构和值都对应上了,那就继续递归判断各自的左子树和各自的右子树是否对应满足条件。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {

// 定义:B是A的真子结构,即B是A的子结构且根节点相等
public:
// 判断B是否为A的真子结构
bool isSub(TreeNode* A, TreeNode* B){ // 两棵树同时同方向遍历,逐个节点判断
// 进入深层递归后,A,B指代的是当前遍历节点
if(B == nullptr) return true; // B节点为空,则B树遍历完了,满足B
if(A == nullptr) return false; // A节点为空,则该方向上A树遍历完了(B还没有),B必然不是A的真子结构
// 当且近当 A与B值相等 且 B的左子树是A的左子树的真子结构,右子树是A的右子树的真子结构
return A->val == B->val && isSub(A->left, B->left) && isSub(A->right, B->right);
}
// 判断B是否为A的子结构
bool isSubStructure(TreeNode* A, TreeNode* B) { // 先序遍历
if(A == nullptr || B == nullptr){
return false;
}
// 要么A含有真子结构B,要么A的左子树或右子树含有子结构B
return isSub(A, B) || isSubStructure(A->left, B) || isSubStructure(A->right, B);
}
};