题目

题解

二叉树结构如下：

//Definition for a binary tree node.
    struct TreeNode {
        int val;
        TreeNode *left;
        TreeNode *right;
        TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    };

1. 双递归法

两个递归函数，一个用来看当前节点是否匹配，一个用来遍历a的所有节点
递归的关键之一在于找到停止条件，注意本题两个递归函数前两行的停止条件

  • 时间复杂度$O(mn)$
  • 空间复杂度$O(min{m,n})$，m是b的节点数，n是n的节点数。最多把其中少的递归完
class Solution {//用两个递归函数
public:
    bool DFS(TreeNode* a, TreeNode* b){
        if(!b) return true;//如果b遍历完成，说明是子树，b的节点a都有
        if(!a) return false;//如果a遍历完成，执行到这说明b没遍历完成，返回false
        return a->val == b->val && DFS(a->left, b->left) && DFS(a->right, b->right);//递归去查ab的左右子树
    }
    bool isSubStructure(TreeNode* A, TreeNode* B) {
        if(!A || !B) return false;//题目说空树不是子结构
        if(DFS(A, B)) return true; //若当前节点是子树，返回ture
        return isSubStructure(A->left, B) || isSubStructure(A->right, B);//递归去查a所有节点
    }
};