leetcode572判断是否子树空间复杂度

Question

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)

Answer 1

图解leetcode572. 另一棵树的子树
使用双层递归，将深度优先搜索递归判断是否包含子树的方法抽取出来，再在主方法中递归每个节点的深搜即可。这种需要递归+遍历的推荐都写成两次递归的这种形式，不建议再额外写类似于leetcode437. 路径总和 III中树的遍历方法，时间复杂度O(m * n)，空间复杂度O(m)，

class Solution {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if(root == null) return false;
        return dfs(root, subRoot) || isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
    }
    public boolean dfs(TreeNode root, TreeNode subRoot){
        if(root == null && subRoot == null) return true;
        if(root == null || subRoot == null) return false;
        if(root.val == subRoot.val) return dfs(root.left, subRoot.left) && dfs(root.right, subRoot.right);
        return false;
    }
}