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.
1class Solution:
2 def isSubtree(self, root, subRoot):
3 if not root:
4 return False
5 if self.isIdentical(root, subRoot):
6 return True
7 return self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)
8
9 def isIdentical(self, s, t):
10 if not s and not t:
11 return True
12 if not s or not t:
13 return False
14 return s.val == t.val and self.isIdentical(s.left, t.left) and self.isIdentical(s.right, t.right)The solution follows a recursive approach where isIdentical checks whether the trees rooted at the current nodes of root and subRoot are the same. If a match is found, it returns true immediately; otherwise, it checks left and right subtree relations.
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.
1var isSubtree = function(root, subRoot) {
2 const rootStr = preorder(root).join(' ');
3 const subRootStr = preorder(subRoot).join(' ');
4 return rootStr.indexOf(subRootStr) !== -1;
5};
6
7var preorder = function(node) {
8 if (!node) {
9 return ['null'];
10 }
11 return [node.val.toString(), ...preorder(node.left), ...preorder(node.right)];
12};This solution generates a preorder traversal string array including 'null' for both trees, concatenates them, and checks if subRoot's string is a substring of root's.