Подсчитать количество листьев в дереве - Неудачный край дела?

Question

В онлайн-оценке меня попросили подсчитать количество листьев на дереве. Дерево дано в виде родительского массива, то есть дерево имеет n узлов с метками 0, 1, 2, .., n-1, и вы передаете массив длины n, где p [i] возвращает меткуродитель узла i, кроме случаев, когда i является корнем дерева, и в этом случае p [i] равно -1.

Полагаю, стоит отметить, что проблема заключалась в том, что проблема описана выше, поэтому не было никаких дополнительных условий, таких как, например, двоичное дерево.

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

def countLeaves(p):
    n = len(p)
    if p is None or n == 0 : return 0
    if n == 1 or n == 2 : return 1

    leaves = set(range(n))
    for i in range(n):
        if p[i] == -1: # i is root of tree with >1 node, can't be a leaf
            leaves.discard(i)
        else: # p[i] is parent of node i, can't be a leaf
            leaves.discard(p[i])

    return len(leaves)

При попытке исправить неудачный «случай маленького дерева»Я также попытался вернуть None, если p равно None, вернуть None, если n == 0, или обе модификации вместе, но безуспешно. Если бы кто-то мог указать, в чем, возможно, была ошибка в моем коде, я был бы очень признателен. Спасибо.

Answer 1

Я бы попробовал это:

def countLeaves(p):
    n = len(p)
    if p is None or n < 2 : return 0

    leaves = set(range(n))
    for i in range(n):
        if p[i] == -1: # i is root of tree with >1 node, can't be a leaf
            leaves.discard(i)
        else: # p[i] is parent of node i, can't be a leaf
            leaves.discard(p[i])

    return len(leaves)

Единственное реальное изменение заключается в том, что он рассматривает деревья с одним узлом без листьев.

Согласно Wolfram Mathworld :

Лист дерева без корней является узлом 1-й вершины. Обратите внимание, что для корневого или посадочного дерева корневая вершина обычно не считается листовым узлом тогда как все остальные узлы степени 1.