leetcode 572题, Subtree of Another Tree
approach1 (参考以下代码), 官方解答说space complextiy是O(M+N) :There will be at most N recursive call to dfs ( or isSubtree). Now, each of these calls will have M recursive calls to isIdentical. Before calling isIdentical, our call stack has at most O(N)elements and might increase to O(N+M)O(N+M) during the call. After calling isIdentical, it will be back to at most O(N) since all elements made by isIdentical are popped out. Hence, the maximum number of elements in the call stack will be M+N.
但是我觉得是O(N),N是root tree的nodes 数量,求举例解释space complexity是O(M+N)
class Solution:
def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
# Check for all subtree rooted at all nodes of tree "root"
def dfs(node):
# If this node is Empty, then no tree is rooted at this Node
# Thus "tree rooted at node" cannot be same as "rooted at subRoot"
# "tree rooted at subRoot" will always be non-empty (constraints)
if node is None:
return False
# If "tree rooted at node" is identical to "tree at subRoot"
elif is_identical(node, subRoot):
return True
# If "tree rooted at node" was not identical.
# Check for tree rooted at children
return dfs(node.left) or dfs(node.right)
def is_identical(node1, node2):
# If any one Node is Empty, both should be Empty
if node1 is None or node2 is None:
return node1 is None and node2 is None
# Both Nodes Value should be Equal
# And their respective left and right subtree should be identical
return (node1.val == node2.val and
is_identical(node1.left, node2.left) and
is_identical(node1.right, node2.right))
# Check for node rooted at "root"
return dfs(root)