subtree_of_another_tree
1from utils import TreeNode 2from typing import Optional 3 4 5# @leet start 6class Solution: 7 def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool: 8 """ 9 This problem asks to return true if one of the trees is a subtree of another. 10 There are 3 ways to do this: 11 1. Naive $O(n^2)$: We check each node to see if they are subtrees. 12 2. Serialization $O(m + n)$: We serialize both trees and validate the subtree property. 13 3. Hashing $O(m + n)$: We hash each subtree of the tree to some value, taking into consideration 14 its left and right sutbrees. 15 16 This function implements the serialization aprpoach. 17 If the node is null, we return a "#" to denote that (any character that doesn't show up works) 18 If the tree is non null, we prefix it with a "^" to denote the start of a subtree 19 And then concatenate the serialization of the left, current node, and right tree. 20 21 We then do serialize both trees, and check if the subtree is in the tree. 22 We can do this in $O(m + n)$ time. 23 """ 24 25 def serialize(node) -> str: 26 if not node: 27 return "#" 28 return f"^{serialize(node.left)}{node.val}{serialize(node.right)}" 29 30 serialized_root = serialize(root) 31 serialized_sub = serialize(subRoot) 32 33 return serialized_sub in serialized_root 34 35 36# @leet end 37 38 39def test(): 40 assert 2 + 2 == 4
class
Solution:
7class Solution: 8 def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool: 9 """ 10 This problem asks to return true if one of the trees is a subtree of another. 11 There are 3 ways to do this: 12 1. Naive $O(n^2)$: We check each node to see if they are subtrees. 13 2. Serialization $O(m + n)$: We serialize both trees and validate the subtree property. 14 3. Hashing $O(m + n)$: We hash each subtree of the tree to some value, taking into consideration 15 its left and right sutbrees. 16 17 This function implements the serialization aprpoach. 18 If the node is null, we return a "#" to denote that (any character that doesn't show up works) 19 If the tree is non null, we prefix it with a "^" to denote the start of a subtree 20 And then concatenate the serialization of the left, current node, and right tree. 21 22 We then do serialize both trees, and check if the subtree is in the tree. 23 We can do this in $O(m + n)$ time. 24 """ 25 26 def serialize(node) -> str: 27 if not node: 28 return "#" 29 return f"^{serialize(node.left)}{node.val}{serialize(node.right)}" 30 31 serialized_root = serialize(root) 32 serialized_sub = serialize(subRoot) 33 34 return serialized_sub in serialized_root
8 def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool: 9 """ 10 This problem asks to return true if one of the trees is a subtree of another. 11 There are 3 ways to do this: 12 1. Naive $O(n^2)$: We check each node to see if they are subtrees. 13 2. Serialization $O(m + n)$: We serialize both trees and validate the subtree property. 14 3. Hashing $O(m + n)$: We hash each subtree of the tree to some value, taking into consideration 15 its left and right sutbrees. 16 17 This function implements the serialization aprpoach. 18 If the node is null, we return a "#" to denote that (any character that doesn't show up works) 19 If the tree is non null, we prefix it with a "^" to denote the start of a subtree 20 And then concatenate the serialization of the left, current node, and right tree. 21 22 We then do serialize both trees, and check if the subtree is in the tree. 23 We can do this in $O(m + n)$ time. 24 """ 25 26 def serialize(node) -> str: 27 if not node: 28 return "#" 29 return f"^{serialize(node.left)}{node.val}{serialize(node.right)}" 30 31 serialized_root = serialize(root) 32 serialized_sub = serialize(subRoot) 33 34 return serialized_sub in serialized_root
This problem asks to return true if one of the trees is a subtree of another. There are 3 ways to do this:
- Naive $O(n^2)$: We check each node to see if they are subtrees.
- Serialization $O(m + n)$: We serialize both trees and validate the subtree property.
- Hashing $O(m + n)$: We hash each subtree of the tree to some value, taking into consideration its left and right sutbrees.
This function implements the serialization aprpoach. If the node is null, we return a "#" to denote that (any character that doesn't show up works) If the tree is non null, we prefix it with a "^" to denote the start of a subtree And then concatenate the serialization of the left, current node, and right tree.
We then do serialize both trees, and check if the subtree is in the tree. We can do this in $O(m + n)$ time.
def
test():