首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >问答首页 >二叉树叶深

二叉树叶深
EN

Stack Overflow用户
提问于 2015-05-05 04:51:34
回答 1查看 1.1K关注 0票数 2

我正在从一个网站上解决以下问题:“编写一个函数来查看一个二叉树是否是”超平衡的“(我们刚刚合成的一种新的树属性)。如果任何两个叶节点的深度相差不大于一个,树就是”超平衡“。”

网站检查两个节点之间深度差异的方法是先进行深度搜索,然后将访问的每个节点的深度附加到称为深度的列表中,只要深度尚未在列表中:

代码语言:javascript
运行
复制
        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

EN

回答 1

Stack Overflow用户

回答已采纳

发布于 2015-05-05 05:01:31

你需要两张支票,差不多.

第一个显然是不够的,因为您可以拥有len(depths)==2和两个>1之间的区别。

第二个条件,正如它所写的,只能在len(depth)完全是2的情况下才能工作。您可能只有后一个条件,但随后需要迭代depth列表中的所有项。

所以从根本上说,它是这样设计的,以尽可能的高效。您可能会认为这是过度优化的情况,因为depths列表的长度永远不会大于3,而且这也是要执行的最大数目。

我会使用像max(depths) - min(depths) > 1这样的东西,它更易读、更直观,对性能的影响也很小。

票数 3
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/30044524

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档