我在回忆录的countUnivalTrees问题中使用了什么时间和空间复杂性？
我尝试了这个挑战，但是花费了太多的时间来执行一些输入。问题如下：
给你一棵二叉树。返回给定二叉树中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 countisUnivalTree与第一次尝试无关，所以我省略了它，不添加额外的代码。我通过了所有的测试。我的计划是有一个O(n)和O(n)空间的时间复杂性。我很难准确理解我的复杂性，以及我的方法是否正确。我的意思是正确地按照我所认为的那样工作：
步骤1:访问树中的每个节点
第二步:从叶到根检查当前根是否是统一的。如果是，则将根保存在memoized中，并将其映射到true。
步骤3:如果当前根节点有一个左、右子节点，而memoized中的该节点映射到true，则意味着它是一个unival树，而不仅仅是检查右和左的子值相同，根值相同，并且是一个unival树，将当前根映射为true。(还考虑到只有一个左子或一个右子的根，并执行这些检查以及O(1)操作)
所以，我想象的是一棵大树，有许多左右交叉的树，但都有相同的值。如果是O(n)一次查看所有节点，其中n是节点的数目，然后当我们弹出堆栈时回传当前节点并映射到true如果是isUnivalTree等等，这是真的吗？
出于某种原因，我觉得我可能遗漏了一种情况，在这种情况下，我应该检查是否是memoized[root.left] = False，如果它是不算的话。不太确定，除了fibonacci编码问题之外，我从来没有回忆录过，所以这对我来说是新的。
Stack Overflow用户
发布于 2022-05-20 15:58:47
我们看不到回忆录，因为我们没有看到你的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)https://stackoverflow.com/questions/72312870
复制相似问题
腾讯云开发者
