小白请教Compute tree height计算树的高度

You are given a description of a rooted tree. Your task is to compute and output its height. Recall
that the height of a (rooted) tree is the maximum depth of a node, or the maximum distance from a
leaf to the root. You are given an arbitrary tree, not necessarily a binary tree.
简单来说就是数组对应的下标就是自己的子节点，如果是-1的话，对应的下标就是根；
Input:
5
4 -1 4 1 1
Output:
3
Explanation:
The input means that there are 5 nodes with numbers from 0 to 4, node 0 is a child of node 4, node
1 is the root, node 2 is a child of node 4, node 3 is a child of node 1 and node 4 is a child of node 1.
The height of this tree is 3, because the number of vertices on the path from root 1 to leaf 2 is 3.
树的结构如下
       1
     /   \
    3    4

       /    \
      0      2  
http://www.geeksforgeeks.org/fin ... ented-parent-array/  Amazon貌似考过
跟这道题其实是一道题，但是这个树不一定只是二叉树。
这道题有很多种做法，可以不用转化成树也可以直接求解。

1. class BinaryTree {
   
2. 
   
3.     // This function fills depth of i'th element in parent[].  The depth is
   
4.     // filled in depth[i].
   
5.     void fillDepth(int parent[], int i, int depth[]) {
   
6. 
   
7.         // If depth[i] is already filled
   
8.         if (depth[i] != 0) {
   
9.             return;
   
10.         }
    
11. 
    
12.         // If node at index i is root
    
13.         if (parent[i] == -1) {
    
14.             depth[i] = 1;
    
15.             return;
    
16.         }
    
17. 
    
18.         // If depth of parent is not evaluated before, then evaluate
    
19.         // depth of parent first
    
20.         if (depth[parent[i]] == 0) {
    
21.             fillDepth(parent, parent[i], depth);
    
22.         }
    
23. 
    
24.         // Depth of this node is depth of parent plus 1
    
25.         depth[i] = depth[parent[i]] + 1;
    
26.     }
    
27. 
    
28.     // This function returns height of binary tree represented by
    
29.     // parent array
    
30.     int findHeight(int parent[], int n) {
    
31.          
    
32.         // Create an array to store depth of all nodes/ and
    
33.         // initialize depth of every node as 0 (an invalid
    
34.         // value). Depth of root is 1
    
35.         int depth[] = new int[n];
    
36.         for (int i = 0; i < n; i++) {
    
37.             depth[i] = 0;
    
38.         }
    
39. 
    
40.         // fill depth of all nodes
    
41.         for (int i = 0; i < n; i++) {
    
42.             fillDepth(parent, i, depth);
    
43.         }
    
44. 
    
45.         // The height of binary tree is maximum of all depths.
    
46.         // Find the maximum value in depth[] and assign it to ht.
    
47.         int ht = depth[0];
    
48.         for (int i = 1; i < n; i++) {
    
49.             if (ht < depth[i]) {
    
50.                 ht = depth[i];
    
51.             }
    
52.         }
    
53.         return ht;
    
54.     }
    
55. 
    
56.     // Driver program to test above functions
    
57.     public static void main(String args[]) {
    
58. 
    
59.         BinaryTree tree = new BinaryTree();
    
60. 
    
61.         // int parent[] = {1, 5, 5, 2, 2, -1, 3};
    
62.         int parent[] = new int[]{-1, 0, 0, 1, 1, 3, 5};
    
63. 
    
64.         int n = parent.length;
    
65.         System.out.println("Height is  " + tree.findHeight(parent, n));
    
66.     }
    
67. }

复制代码

但是现在如果想用树的方法如何做呢？ 构建树的结构的时候，是不是需要用一个hashmap把数字和对应的树节点联系起来，才方便调用树节点？
还有应该怎么计算非二叉树的高度呢，递归，DFS,BFS，具体如何实现呢？非常感谢！！！！

构建树的结构...就是构建图啊.
一个List<List<Integer>> graph;
一个boolean[] isVisted;

Recursion: height(root) =  Math.max(height(root.left), height(root.right)+1;
DFS: dfs(root), 走一遍维护一个max;
BFS: layer by layer search....最后一个layer的层数就是height......
没有胡萝卜......ToT

2叉树根n叉树没区别啊，递归的话直接max (child.height) +1就行了。。。
聪哥，求胡萝卜