题目描述

输入两棵二叉树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$

---

算法

(DFS,暴力遍历) $O(nm)$

算法步骤：

1. 遍历树 $root$ 中的每个节点 $s$ 都与子树 $subRoot$ 进行匹配
2. 递归匹配子树 $s$ 和 $subRoot$ 中的每个节点，如果每个节点都相同，则匹配成功。

边界：

1. 在 isSubStructure() 中如果 $subRoot$ 为空，题目已知空树不是任何树的子结构，所以返回 $false$。
2. 在 dfs() 中，当 $q$ 为空时不需要判断 $p$ 是否为空，只要保证 $q$ 是 $p$ 的子结构即可，不需要完全匹配。

时间复杂度

树 $root$ 中的每个节点都需要与子树 $subRoot$ 进行匹配，所以时间复杂度为 $O(nm)$，$n$ 为 $root$ 的节点个数，$m$ 为 $subRoot$ 的节点个数。

空间复杂度

一次匹配时最多需要 $O(max(d_1, d_2))$ 的空间复杂度，$d_1$ 表示 $root$ 的子树匹配结束时的深度，$d_2$ 表示 $subRoot$ 匹配结束时的深度。

C++ 代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool dfs(TreeNode* p, TreeNode* q) {
        if (!q) return true;
        if (!p || p->val != q->val) return false;
        return dfs(p->left, q->left) && dfs(p->right, q->right);
    }

    bool isSubStructure(TreeNode* root, TreeNode* subRoot) {
        if (!root || !subRoot) return false;
        if (dfs(root, subRoot)) return true;
        return isSubStructure(root->left, subRoot) || isSubStructure(root->right, subRoot);
    }
};