剑指 Offer 26. 树的子结构

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

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

例如:
给定的树 A:

3
/
4 5
/
1 2

给定的树 B：

4
/
1

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

示例 1：

输入：A = [1,2,3], B = [3,1]
输出：false

示例 2：

输入：A = [3,4,5,1,2], B = [4,1]
输出：true

限制：

0 <= 节点个数 <= 10000

解题思路

1. 先序遍历树A中的每个节点na
2. 判断树A中以na为根节点的子树是否包含树B 对应函数recur（A，B）

recur(A,B)

1. 终止条件：
   1. 当节点B为空：说明树B匹配完成，返回true
   2. 当节点A为空，说明已经越过树A叶子节点，返回false
   3. 当节点A和节点B的值不同，返回false
2. 返回值
   1. 判断A和B的左子树节点是否相等，recur(A->left,B->right)
   2. 判断A和B的右子树节点是否相等, recur(A->right,B->right)

isSubStructure(A,B)

1. 空值处理，返回false
2. 若树B是树A的子结构，满足以下三种情况
   1. 以节点A为根节点的子树包含B recur(A,B)
   2. 树B是树A左子树的子结构，对应 isSubStructure(A->left,B)
   3. 树B是树A右子树的子结构，对应 isSubStructure(A->right,B)；

AC代码

class Solution {
public:
    bool isSubStructure(TreeNode* A, TreeNode* B) {
        if(A == NULL||B == NULL) return false;
        return recur(A,B)||isSubStructure(A->left,B)||isSubStructure(A->right,B);
    }
    bool recur(TreeNode* A,TreeNode* B){
        if(B == NULL)   return true;
        if(A == NULL || A->val != B->val)   return false;
        return recur(A->left,B->left)&&recur(A->right,B->right);
    }
};