This approach involves using a recursive function to traverse the root tree and checking for a matching subtree starting from every node. A helper function can be used to check if trees rooted at specific nodes are identical.
Time Complexity: O(N*M), where N is the number of nodes in the root tree and M is the number of nodes in subRoot tree.
Space Complexity: O(min(N, M)), depending on the tree height during recursion.
1public class Solution {
2 public bool IsSubtree(TreeNode root, TreeNode subRoot) {
3 if (root == null) return false;
4 if (IsIdentical(root, subRoot)) return true;
5 return IsSubtree(root.left, subRoot) || IsSubtree(root.right, subRoot);
6 }
7
8 private bool IsIdentical(TreeNode s, TreeNode t) {
9 if (s == null && t == null) return true;
10 if (s == null || t == null) return false;
11 return s.val == t.val && IsIdentical(s.left, t.left) && IsIdentical(s.right, t.right);
12 }
13}The C# solution utilizes recursion with two functions: IsSubtree performs tree traversal, while IsIdentical checks if the trees rooted at the current pair of nodes are identical.
Another approach to solving this problem is by converting the trees into their preorder traversal strings with marker symbols for nulls, and then checking if the subRoot string is a substring of the root string.
Time Complexity: O(N + M + N*M), where N and M are the sizes of the trees.
Space Complexity: O(N + M), for the preorder traversal strings.
1#include <stdbool.h>
2#include <string.h>
3#include <stdio.h>
4
5struct TreeNode {
6 int val;
7 struct TreeNode *left, *right;
8};
9
10void preorder(struct TreeNode* node, char *s) {
11 if (node == NULL) {
12 strcat(s, "null ");
13 return;
14 }
15 char buffer[12];
16 sprintf(buffer, "%d ", node->val);
17 strcat(s, buffer);
18 preorder(node->left, s);
19 preorder(node->right, s);
20}
21
22bool isSubstring(char* s1, char* s2) {
23 return strstr(s1, s2) != NULL;
24}
25
26bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot) {
27 char rootString[10000] = "";
28 char subRootString[10000] = "";
29 preorder(root, rootString);
30 preorder(subRoot, subRootString);
31 return isSubstring(rootString, subRootString);
32}This approach serializes both trees using a preorder traversal which handles null nodes explicitly. The serialized string of subRoot is then checked as a substring within that of root.