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 <bits/stdc++.h>
2using namespace std;
3
4struct TreeNode {
5 int val;
6 TreeNode *left, *right;
7};
8
9bool isIdentical(TreeNode* s, 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(TreeNode* root, 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}This solution uses the same logic as the C solution, with helper functions isIdentical and isSubtree to recursively match subtrees or check subtrees under left and right children.
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.
1public class Solution {
2 public bool IsSubtree(TreeNode root, TreeNode subRoot) {
3 string rootStr = Preorder(root, new System.Text.StringBuilder()).ToString();
4 string subRootStr = Preorder(subRoot, new System.Text.StringBuilder()).ToString();
5 return rootStr.Contains(subRootStr);
6 }
7
8 private StringBuilder Preorder(TreeNode node, StringBuilder sb) {
9 if (node == null) {
10 sb.Append("null ");
11 return sb;
12 }
13 sb.Append(node.val).Append(' ');
14 Preorder(node.left, sb);
15 Preorder(node.right, sb);
16 return sb;
17 }
18}The C# solution serializes the trees to preorder strings, including null representations, then checks if subRoot's string occurs in root's string using StringBuilder for flexibility.