leetcode：572. 另一棵树的子树

题目

给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。

二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。

示例 1：
[简单] 572. 另一棵树的子树 - 图1

  1. 输入：root = [3,4,5,1,2], subRoot = [4,1,2]
  2. 输出：true

示例 2：
[简单] 572. 另一棵树的子树 - 图2

  1. 输入：root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
  2. 输出：false

解答 & 代码

DFS 遍历二叉树 root 的每个节点，记为 node

  • 比较 node 和 subRoot 的值是否相同，若相同，则 DFS 同时遍历 node 子树和 subRoot 树，判定两棵树是否相同

    1. /**
    2. * Definition for a binary tree node.
    3. * struct TreeNode {
    4. *     int val;
    5. *     TreeNode *left;
    6. *     TreeNode *right;
    7. *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
    8. *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    9. *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
    10. * };
    11. */
    12. class Solution {
    13. private:
    14.   // DFS 比较两棵树是否相同
    15.   bool isSameTree(TreeNode* root1, TreeNode* root2)
    16.   {
    17.       if(root1 == nullptr && root2 == nullptr)
    18.           return true;
    19.       if(root1 == nullptr || root2 == nullptr)
    20.           return false;
    21.       return root1->val == root2->val && 
    22.               isSameTree(root1->left, root2->left) &&
    23.               isSameTree(root1->right, root2->right);
    24.   }
    25. public:
    26.   // DFS 检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树
    27.   bool isSubtree(TreeNode* root, TreeNode* subRoot) {
    28.       if(subRoot == nullptr)
    29.           return true;
    30.       if(root == nullptr)
    31.           return false;
    33.       return (root->val == subRoot->val && isSameTree(root, subRoot)) ||
    34.               isSubtree(root->left, subRoot) ||
    35.               isSubtree(root->right, subRoot);
    36.   }
    37. };

    复杂度分析：设二叉树 root 节点数为 m，二叉树 subRoot 节点数为 n

  • 时间复杂度 O(mn)：dfs 遍历二叉树 root 的每个节点 node，时间复杂度 O(m)；对每个节点 node，判断以 node 为根节点的树和 subRoot 是否相同，时间复杂度 O(n)

  • 空间复杂度 O(log n)：

执行结果：

  1. 执行结果：通过
  3. 执行用时：20 ms, 在所有 C++ 提交中击败了 68.27% 的用户
  4. 内存消耗：27.9 MB, 在所有 C++ 提交中击败了 95.12% 的用户