zkkKillua's Blog
0%

572.另一棵树的子树

发表于 更新于 分类于

相关题目：

100. 相同的树

1. 递归

t是s的子树，则可能是：

  1. s的子树
  2. s的左子树的子树
  3. s的右子树的子树

而判断是否是子树的过程，就是判断当前s中为根的节点的子树与t树是否相同。
时间复杂度：这里与“相同的树”遍历所有节点O(n)不同，此处最差需要看s的每一个节点对应的子树是否是与t相同的，所以需要O(|s| * |t|).
空间复杂度：递归栈最深是O(n). 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isSameTree(TreeNode* s, TreeNode* t) {
        if (s == nullptr && t == nullptr)
            return true;
        if (s == nullptr || t == nullptr)
            return false;
        if (s->val != t->val)
            return false;
        return isSameTree(s->left, t->left) && isSameTree(s->right, t->right);
    }

    bool isSubtree(TreeNode* s, TreeNode* t) {
        if (s == nullptr && t == nullptr)
            return true;
        if (s == nullptr)
            return false;
        if (t == nullptr)
            return true;
        if (s->val != t->val)   // 如果s和t的根节点的值不等，则t只可能是s的左或右子树的子树
            return isSubtree(s->left, t) || isSubtree(s->right, t);
        else                    // 如果s和t的根节点的值相等，则t与s可能相同，而如果不同则只可能是s的左或右子树的子树
            return isSameTree(s, t) || isSubtree(s->left, t) || isSubtree(s->right, t);
    }
};