我正在从一个网站上解决以下问题:“编写一个函数来查看一个二叉树是否是”超平衡的“(我们刚刚合成的一种新的树属性)。如果任何两个叶节点的深度相差不大于一个,树就是”超平衡“。”
网站检查两个节点之间深度差异的方法是先进行深度搜索,然后将访问的每个节点的深度附加到称为深度的列表中,只要深度尚未在列表中:
if depth not in depths:
depths.append(depth)
# two ways we might now have an unbalanced tree:
# 1) more than 2 different leaf depths
# 2) 2 leaf depths that are more than 1 apart
if (len(depths) > 2) or \
(len(depths) == 2 and abs(depths[0] - depths[1]) > 1):
return False
我不明白的是,为什么我们要检查这两种方式?仅仅检查一下条件是否有两个以上不同的叶深,还是两个不同的叶深相隔,难道不就足够了吗?为什么两张支票都有用呢?
代码/问题引用自source:InterviewCake.com
发布于 2015-05-05 05:01:31
你需要两张支票,差不多.
第一个显然是不够的,因为您可以拥有len(depths)==2
和两个>1
之间的区别。
第二个条件,正如它所写的,只能在len(depth)
完全是2
的情况下才能工作。您可能只有后一个条件,但随后需要迭代depth
列表中的所有项。
所以从根本上说,它是这样设计的,以尽可能的高效。您可能会认为这是过度优化的情况,因为depths
列表的长度永远不会大于3
,而且这也是要执行的最大数目。
我会使用像max(depths) - min(depths) > 1
这样的东西,它更易读、更直观,对性能的影响也很小。
https://stackoverflow.com/questions/30044524
复制相似问题