Вычисление высоты дерева C #

Question

Я писал этот код для вычисления высоты дерева в c #.вход для этого вопроса будет первым: количество узлов, а затем количество для каждого из них.тогда на выходе будет высота дерева.

вход

5

4 -1 4 1 1

выход 3

 public long Solve(long nodeCount, long[] tree)
    {
        List<long>[] Node = new List<long>[nodeCount];
        long root = 0; 

        for(int i =0;i<nodeCount;i++ )
        {
            Node[i] = new List<long>();
        }

        for(int j =0; j<nodeCount;j++)
        {
            if (tree[j] == -1)
                root = j;
            else
                Node[tree[j]].Add(j);
        }

        Queue<long> Q = new Queue<long>();
        Q.Enqueue(root);
        long Height = 0;

        while(Q.Any())
        {

            for(int i =0; i<Q.Count(); i++)
            {
                long nodee = Q.Dequeue();

                if(Node[nodee] != null)
                {
                    foreach(long N in Node[nodee])
                    {
                        Q.Enqueue(N);
                    }
                }
            }

           Height = Height+1;
        }
        return Height;
    }

этот код возвращает неверные результаты в мои тесты.в чем проблема?

Answer 1

Вы можете поменять направление указателя узлов дерева в O(n) при использовании 2 массивов (в качестве указателя для 2 дочерних элементов индексированного узла):

int size = 5;
int arr[size] = {4, -1, 4, 1, 1};
int a[size];
int b[size];
for (int i = 0; i < size; i++) {
    a[i] = -1;
    b[i] = -1;
} // I'm not c++ expert (I guess there are better way of init array with the same value...
int root = -1;
for (int i = 0; i < size; i++) {
    if (arr[i] == -1)
        root = i;
    else if (a[arr[i]] != -1)
        b[arr[i]] = i;
    else 
        a[arr[i]] = i;
}

Это делается в цикле 1 for.

Теперь вы можете использовать эти 2 массива, чтобы получить ваш рост рекурсивным способом:

int findHeight(int current, int count, int a[], int b[]) {
    int maxV = count;
    if (a[current] > -1)
        maxV = max(findHeight(a[current], count + 1, a, b), maxV);
    if (b[current] > -1)
        maxV = max(findHeight(b[current], count + 1, a, b), maxV);
    return maxV;
} 

Выполните это с помощью:

int height = findHeight(root, 1, a, b); //(as root is the first level)

Общая сложность времени выполнения равна O(n)

Надеюсь, что поможет