Sponsored
Sponsored
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.
1#include <stdbool.h>
2
3struct TreeNode {
4 int val;
5 struct TreeNode *left;
6 struct TreeNode *right;
7};
8
9bool isIdentical(struct TreeNode* s, struct TreeNode* t) {
10 if (!s && !t) return true;
11 if (!s || !t) return false;
12 return (s->val == t->val) && isIdentical(s->left, t->left) && isIdentical(s->right, t->right);
13}
14
15bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot) {
16 if (!root) return false;
17 if (isIdentical(root, subRoot)) return true;
18 return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
19}The function isIdentical compares two trees recursively to check if they are identical. The main function isSubtree checks the root node against the subRoot using isIdentical and then calls itself recursively on the left and right children of the root node.
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 <string>
#include <sstream>
struct TreeNode {
int val;
TreeNode *left, *right;
};
void getPreorder(TreeNode* node, std::ostringstream& out) {
if (node == NULL) {
out << "null ";
return;
}
out << node->val << " ";
getPreorder(node->left, out);
getPreorder(node->right, out);
}
bool isSubtree(TreeNode* root, TreeNode* subRoot) {
std::ostringstream rootStream, subRootStream;
getPreorder(root, rootStream);
getPreorder(subRoot, subRootStream);
return rootStream.str().find(subRootStream.str()) != std::string::npos;
}Using ostringstream to accumulate the preorder traversal string, this method checks if serialized subRoot is a substring of the serialized root.