nikunjsoni

572

Jun 27th, 2021
97
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  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. public:
  14.     bool isSubtree(TreeNode* s, TreeNode* t) {
  15.         if(!s) return false;
  16.         if(isSame(s,t)) return true;
  17.         return isSubtree(s->left,t) || isSubtree(s->right,t);
  18.     }
  19.     bool isSame(TreeNode *s, TreeNode *t){
  20.         if (!s && !t) return true;
  21.         if (!s || !t) return false;
  22.         if (s->val != t->val) return false;
  23.         return isSame(s->left, t->left) && isSame(s->right, t->right);
  24.     }
  25. };
  26.  
  27. -------------------
  28.  
  29. /**
  30.  * Definition for a binary tree node.
  31.  * struct TreeNode {
  32.  *     int val;
  33.  *     TreeNode *left;
  34.  *     TreeNode *right;
  35.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  36.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  37.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  38.  * };
  39.  */
  40. class Solution {
  41. public:
  42.     bool isSubtree(TreeNode* root, TreeNode* subRoot) {
  43.         string text = serialize(root);
  44.         string pat = serialize(subRoot);
  45.         return text.find(pat) != string::npos;
  46.     }
  47.    
  48.     std::hash<std::string> str_hash;
  49.     string serialize(TreeNode *root){
  50.         if(!root) return "#";
  51.         return to_string(str_hash(to_string(root->val)))+","+serialize(root->left)+","+serialize(root->right);
  52.     }
  53.    
  54. };
RAW Paste Data