Массив деревьев в поисках родителей и родителей и кратчайшего пути к корню

Question

Я хочу найти кратчайший путь от ребенка к его родителю, дедушке и бабушке и, в конце концов, к корню.

Например, input 0 0 0 1 2 означает, что:

input[1] parent is 0 (route = 1)
input[2] also has parent 0 (route = 1) 
input[3] has parent 1 which has parent 0 (route = 2)
input[4] has parent 2 which has parent 0 (route = 2)

Код на данный момент:

Создан массив с именем targetNodes, который содержит 0 0 0 1 2,

System.out.print( "0 " );

for ( int x = 1; x < arrayLength; x++ )
{

  int depth = 1;
  int parent = 0;

  while ( targetNodes[x] != 0 ) 
  {
      depth++;
      targetNodes[x] = targetNodes[ targetNodes[x] ] ;
  }   

  // output shortest path from node to root for every node
  System.out.print( depth + " " );

}

System.out.print("\n");

Мой пример работает и с вводом: 0 0 0 1 2 выводит: 0 1 1 2 2, но для ввода: 0 0 1 2 1 4 выводит: 0 1 2 2 2 2, когда правильный вывод будет: 0 1 2 3 2 3

Не уверен, что я делаю неправильно, я думаю, это логика

Answer 1

Это на самом деле довольно просто.Самым сложным было преобразовать данные для модульных тестов, чтобы их можно было эффективно набирать.

package so7455242;

import static org.junit.Assert.*;

import org.junit.Test;

import com.google.common.primitives.Ints;

public class DistanceFinder {

  private static int[] findPathLengths(int[] parent) {
    int[] distances = new int[parent.length];
    for (int i = 0; i < parent.length; i++) {
      int distance = 0;
      for (int node = i; node != 0; node = parent[node]) {
        distance++;
      }
      distances[i] = distance;
    }
    return distances;
  }

  private static int[] toIntArray(String s) {
    String[] words = s.split(" ");
    int[] ints = new int[words.length];
    for (int i = 0; i < ints.length; i++) {
      ints[i] = Integer.parseInt(words[i]);
    }
    return ints;
  }

  private static void testcase(String expected, String input) {
    int[] nodeDefinitions = toIntArray(input);
    int[] pathLengths = findPathLengths(nodeDefinitions);
    String actual = Ints.join(" ", pathLengths);
    assertEquals(expected, actual);
  }

  @Test
  public void test() {
    testcase("0 1 1 2 2", "0 0 0 1 2");
    testcase("0 1 2 3 2 3", "0 0 1 2 1 4");
  }

}