{"id":2239,"date":"2018-03-19T21:34:25","date_gmt":"2018-03-20T04:34:25","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=2239"},"modified":"2018-03-21T09:20:23","modified_gmt":"2018-03-21T16:20:23","slug":"leetcode-572-subtree-of-another-tree","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/tree\/leetcode-572-subtree-of-another-tree\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 572. Subtree of Another Tree"},"content":{"rendered":"

Problem<\/strong><\/h1>\n

\u9898\u76ee\u5927\u610f\uff1a\u5224\u65ad\u4e00\u68f5\u6811\u662f\u4e0d\u662f\u53e6\u5916\u4e00\u68f5\u6811\u7684\u5b50\u6811\u3002<\/p>\n

https:\/\/leetcode.com\/problems\/subtree-of-another-tree\/description\/<\/a><\/p>\n

Given two non-empty binary trees\u00a0s<\/b>\u00a0and\u00a0t<\/b>, check whether tree\u00a0t<\/b>\u00a0has exactly the same structure and node values with a subtree of\u00a0s<\/b>. A subtree of\u00a0s<\/b>\u00a0is a tree consists of a node in\u00a0s<\/b>\u00a0and all of this node’s descendants. The tree\u00a0s<\/b>\u00a0could also be considered as a subtree of itself.<\/p>\n

Example 1:<\/b>
\nGiven tree s:<\/p>\n

     3\r\n    \/ \\\r\n   4   5\r\n  \/ \\\r\n 1   2\r\n<\/pre>\n
Given tree t:<\/p>\n
   4 \r\n  \/ \\\r\n 1   2\r\n<\/pre>\n
Return\u00a0true<\/b>, because t has the same structure and node values with a subtree of s.<\/p>\n
Example 2:<\/b>
\nGiven tree s:<\/p>\n
     3\r\n    \/ \\\r\n   4   5\r\n  \/ \\\r\n 1   2\r\n    \/\r\n   0\r\n<\/pre>\n
Given tree t:<\/p>\n
   4\r\n  \/ \\\r\n 1   2\r\n<\/pre>\n
Return\u00a0false<\/b>.<\/p>\n
Solution: Recursion<\/h1>\n
Time complexity: O(max(n, m))<\/p>\n
Space complexity: O(max(n, m))<\/p>\n
C++<\/p>\n
\/\/ Author: Huahua\r\n\/\/ Running time: 29 ms\r\nclass Solution {\r\npublic:\r\n  bool isSubtree(TreeNode* s, TreeNode* t) {\r\n    if (t == nullptr) return true;\r\n    if (s == nullptr) return false;\r\n    if (isSameTree(s, t)) return true;\r\n    return isSubtree(s->left, t) || isSubtree(s->right, t);\r\n  }\r\nprivate:\r\n  bool isSameTree(TreeNode* s, TreeNode* t) {\r\n    if (s == nullptr && t == nullptr) return true;\r\n    if (s == nullptr || t == nullptr) return false;\r\n    return (s->val == t->val) \r\n           && isSameTree(s->left, t->left) \r\n           && isSameTree(s->right, t->right);\r\n  }\r\n};<\/pre>\n
Related Problems<\/strong><\/h1>\n