剑指 Offer 26. 树的子结构

剑指 Offer 26. 树的子结构 题目

力扣

思路

首先，如果A或B为空，就返回false。

再考虑三种情况：

• B是以 节点 AA为根节点的子树 包含树 B
• 树 BB 是 树 AA左子树 的子结构
• 树 BB 是 树 A 右子树 的子结构

判断B是否是以 节点 AA为根节点的子树 包含树 B，终止条件：

• B为空，表示B匹配完了，返回true
• A为空，表示B没得匹配了，返回false
• A和B的值不同，返回false

如果以上都不符合，返回判断A左结点和B左结点是否是子树关系与上判断A右结点和B右结点是否是子树关系。

代码

class Solution {
public:
    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); 
    }
    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);
    }
};