我在回忆的countunivaltrees问题上使用什么时间和空间复杂性

Question

我尝试了这个挑战，但花了太长时间才能执行一些投入。问题如下

，您得到了一棵二进制树。在给定的二进制树中返回Unival子树的计数。在Unival树中，所有节点下方的所有节点都具有与根的数据相同的值。

我的第一次尝试失败，因为时间复杂性

def countUnivalTrees(tree):
    if tree is None:
        return 0

    leftCount = countUnivalTrees(tree.left)
    rightCount = countUnivalTrees(tree.right)

    count = leftCount + rightCount

    if isUnivalTree(tree, tree.value):
        count += 1

    return count


def isUnivalTree(tree, value):
    if tree is None:
        return True

    if tree.value != value:
        return False

    if tree.left is None and tree.right is None:
        return True

    return isUnivalTree(tree.left, value) and isUnivalTree(tree.right, value)

给出了正确的答案，但可能需要太长的执行时间一些给定的输入。

我的第二种方法是记住我已经看到的东西。

def countUnivalTrees(root, memoized={}):
    if root is None:
        return 0

    memoized[root] = False

    leftCount = countUnivalTrees(root.left, memoized)
    rightCount = countUnivalTrees(root.right, memoized)

    count = leftCount + rightCount

    if root.left is not None and root.right is not None:
        if memoized[root.left] and memoized[root.right] and root.left.value == root.right.value and root.value == root.left.value:
            memoized[root] = True
            count += 1
    elif root.left is not None:
        if memoized[root.left] and root.value == root.left.value:
            memoized[root] = True
            count += 1
    elif root.right is not None:
        if memoized[root.right] and root.value == root.right.value:
            memoized[root] = True
            count += 1
    else:
        if isUnivalTree(root, root.value):
            memoized[root] = True
            count += 1

    return count

isunivaltree是第一次尝试的固定，因此我省略了它以不添加额外的代码。我能够通过所有测试。我的计划是具有o（n）和o（n） space的时间复杂性。我很难确切了解我的复杂性以及我的方法是否正确。通过正确，我的意思是准确地工作我应该是：

步骤1：访问树中的每个节点

：从叶到根检查电流根是单个单位。如果将root保存在记忆中，然后将其映射到true。

步骤3：如果当前的根节点具有左和右子节点，并且该节点在中记忆映射到true这意味着它是一个Unival树，而不是检查右和左子女值是相同和根值相同的，并且是一个单词树，将当前的根并映射到true。 （还要考虑只有一个剩下一个孩子或只有一个右孩子的根，并且执行这些检查o（1）操作），

所以我想象一棵大树的左右跨度，但所有相同的值。确实，我们正在查看所有节点，一旦O（n），n是节点的数量，然后当我们弹出堆栈记忆时，将当前的节点记忆并映射到True，如果isunivaltree and>很快。

由于某种原因，我觉得我可能会缺少一个情况，我应该检查是否回忆[root.left] = false，并且如果它不计数。不确定，除了fibonacci编码问题之外，我从未回忆过，所以这对我来说是新的。

Answer 1

我们看不到回忆，因为我们看不到您的isunivaltree。但是，如果它很快，那么它肯定是o（n）时间，因为您只访问每个节点最多2倍（一次计数树，一次查看是否标记为Unival），您将其记忆。

但是没有必要记忆。只需一口气返回所需的所有上下文即可。如果那比您想使用的更混乱，那就有一个琐碎的包装器。

def unival_trees (root):
    return _unival_trees_and_meta(root)[0]

def _unival_trees_and_meta(root):
    if root.left is None:
        if root.right is None:
            return (1, True, root.value)
        else:
            count_right, right_is_unival, right_value = _unival_trees_and_meta(root.right)
            if right_is_unival and root.value == right_value:
                return (count_right + 1, True, root.value)
            else:
                return (count_right, False, root.value)
    else:
        count_left, left_is_unival, left_value = _unival_trees_and_meta(root.left)
        if root.right is None:
            if left_is_unival and left_value == root.value:
                return (count_left + 1, True, root.value)
            else:
                return (count_left, False, root.value)
        else:
            count_right, right_is_unival, right_value = _unival_trees_and_meta(root.right)
            if left_is_unival and right_is_unival and left_value == right_value and left_value == root.value:
                return (count_right + count_left + 1, True, root.value)
            else:
                return (count_right + count_left, False, root.value)