Двоичная глубина дерева у листьев

Question

Я решаю следующую проблему на веб-сайте: «Напишите функцию, чтобы увидеть, является ли бинарное дерево« супербалансированным »(новое свойство дерева, которое мы только что создали). Дерево« супербалансированное » если разница между глубинами любых двух листовых узлов не больше единицы ».

Способ, которым веб-сайт проверяет разницу в глубинах между двумя узлами, - это выполнить поиск по глубине и затем добавить глубину каждого посещенного узла в список, называемый глубинами, если глубина еще не указана в списке:

 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 

Что я не понимаю, почему мы должны проверять оба пути? Не было бы достаточно, чтобы просто проверить, есть ли более двух разных глубин листьев или две разные глубины листьев, более одного? Почему полезно иметь обе проверки?

код/​​Вопрос цитаты из источника: InterviewCake.com

Answer 1

вам нужны обе проверки, вроде ...

первый явно не хватает, так как вы можете иметь len(depths)==2 и разница между этими двумя >1.

2-е условие, как написано, может работать, только если len(depth) - это точно 2. у вас может быть только последнее условие, но тогда вам нужно будет перебирать все элементы в списке depth.

поэтому в основном он разработан таким образом, чтобы быть максимально эффективным. вы можете утверждать, что это случай чрезмерной оптимизации, поскольку длина списка depths никогда не будет больше 3, и это также максимальное число, которое проверит эта проверка.

Я бы пошел с чем-то вроде max(depths) - min(depths) > 1, который является более читаемым и интуитивным и оказывает незначительное влияние на производительность.