叶子处的二叉树深度

Question

我正在解决网站上的以下问题："Write a function to see if a binary tree is "superbalanced"（我们刚刚制作的新树属性）。如果任意两个叶节点的深度之差不大于 1，则一棵树是 "superbalanced"。"

网站检查两个节点之间深度差异的方式是进行深度优先搜索，然后将访问过的每个节点的深度附加到称为深度的列表中，只要该深度不在列表中即可:

        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

我不明白的是，为什么我们必须检查两种方式？仅仅检查条件是否有超过 2 个不同的叶深度或 2 个不同的叶深度相距超过 1 个是否足够？为什么同时进行这两项检查很有用？

Code/Question 引用自 source:InterviewCake.com

Answer 1

你需要两张支票，有点...

第一个显然不够，因为你可以有 len(depths)==2 和两者之间的差异 >1.

第二个条件，如其所写，只有在 len(depth) 正好是 2 时才有效。你可能只有后一种情况，但你需要遍历 depth 列表中的所有项目。

所以基本上它的设计方式是尽可能高效。您可能会争辩说这是过度优化的情况，因为 depths 列表的长度永远不会大于 3 并且这也是此检查将执行的最大数量。

我会选择 max(depths) - min(depths) > 1 这样的东西，它更具可读性和直观性，对性能的影响可以忽略不计。

叶子处的二叉树深度

Binary tree depth at leaves

python

tree

tree-traversal

depth-first-search

depth