LeetCode-剑指26-树的子结构

1、递归

为了比较B是否为A的子结构，我们可以定义一个函数compare用于比较当前的两个树节点A和B中，B是否为A的子结构。在该函数内部我们考虑这样几种情况：1、当B为空节点时，此时满足子结构的定义返回true；2、当A为空或A与B的值不等时，此时返回false；3、除以上情况外，我们返回当前节点左右子节点的compare的并。

定义完compare之后，我们考虑主函数isSubStructure中的结构：1、当A或B为空时显然返回false；2、当其二者不为空时，我们返回当前节点以及当前节点左右子节点的compare的交。

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

    bool isSubStructure(TreeNode *A, TreeNode *B) {
        if (!A || !B) return false;
        return compare(A, B) || isSubStructure(A->left, B) || isSubStructure(A->right, B);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13