leetcode

0 class Solution {

1 bool strStr(string haystack, string needle) {

2 int m = haystack.size(), n = needle.size();

3 vector<int> table(needle.size(), 0);

4

5 for (int len = 0, j = 1; j < n;) {

6 if (needle[j] == needle[len])

7 table[j++] = ++len;

8 else if (len)

9 len = table[len - 1];

10 else

11 table[j++] = 0;

12 }

13

14 for (int i = 0, j = 0; i < m;) {

15 if (haystack[i] == needle[j]) i++, j++;

16 if (j == n) return true;

17 if (i < m && haystack[i] != needle[j]) j ? j = table[j - 1] : i++;

18 }

19

20 return false;

21 }

22

23 string tree_preorder_string(TreeNode *root) {

24 if (!root) return "";

25 string res = "";

26 stack<TreeNode *> st;

27

28 st.push(root);

29 while (!st.empty()) {

30 TreeNode *root = st.top();

31 st.pop();

32 res += root ? "_" + to_string(root->val) : "#";

33 if (!root) continue;

34 st.push(root->right);

35 st.push(root->left);

36 }

37 return res;

38 }

39

40 public:

41 bool isSubtree(TreeNode *root, TreeNode *subRoot) {

42 string tree = tree_preorder_string(root);

43 string sub = tree_preorder_string(subRoot);

44 return strStr(tree, sub);

45 }

46 };