java - 数组树找到 parent 和他们的 parent 以及到根的最短路径

Question

我想找到从一个 child 到他的 parent ，到祖 parent ，最后到根的最短路线。

例如，输入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");
  }

}