Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- 1.
- A tree, (NOT NECESSARILY BINARY), has nodes numbered 0 to N-1. An array has indices ranging from 0 to N-1.
- The indices denote the node ids and values denote the ids of parents. A value of -1 at some index k denotes
- that node with id k is the root. For ex:
- 3 3 3 -1 2
- 0 1 2 3 4
- In the above, nodes with ids 0, 1 & 2 have 3 as parent. 3 is the root as its parent = -1 and 2 is the parent of node id 4.
- Given such an array, find the heig ht of the tree.
- keyword:
- a tree - children maybe > 2
- 0 - N - 1, total N nodes
- customize array[i] - i - node id, array[i] is node id i's parent
- -1 is special: root node
- ask: given such an array, find the hight of the tree
- 3 3 3 -1 2
- 0 1 2 3 4
- reconstruct:
- parent <- child
- 3 <- 0
- 3 <- 1
- 3 <- 2
- -1 <- 3 root
- 2 <- 4
- above height of tree is 3
- 0 -> 3 -> -1 -> 0 -> height[0] = 2, height[3] = 1,
- 1 -> 3 -> -1 -> 1 + height[3] = 2
- 2 -> 3 -> - 1 -> 1 + height[3] = 2
- 3 -> -1
- 4 -> 2 -> 3-> -1
- line 36 -> 3 brute force solution O(n * height of tree)
- line 34, 2 -> 3
- public static int FindHeightOfTree(int[] numbers) // indexWithParentId
- {
- if(numbers == null)
- return new int[0];
- var length = numbers.Length;
- var heightIds = new int[length];
- for(int index = 0; index < length; index++)
- {
- if(heightIds[index] > 0)
- continue;
- // find the path for id = index, save height along the path for each id
- //3 3 3 -1 2
- //0 1 2 3 4
- var iterate = index; // 0
- var pathLength = 0;
- var pathList = new List<int>();
- // index = 3
- // iterate = index = 3
- // numbers[iterate] = -1
- while(iterate != -1) // deadloop - no problem ->
- {
- var visit = numbers[iterate]; // 3
- iterate = visit; // 3
- // height -> no more loop -> exit
- if(height[visit] > 0) //
- {
- pathLength += height[visit];
- break;
- }
- pathList.Add(visit); // 3
- pathLength++;
- }
- // add one more while loop -> replace the list
- heightIds[index] = pathLength;
- for(int i = 0; i < pathList.Length; i++)
- {
- if(height[pathList[i]] != 0) // duplicate -> more than O(n)
- height[pathList[i]] = pathLength - i;
- }
- }
- return heightIds.Max();
- }
- -1 0 1 2 3
- 0 1 2 3 4
- 0 - > -1
- 1 -> 0 -> -1
- 2 -> 1 -> look up height
- 3 -> 2 -> look up height
- 4->3 -> look up height
Add Comment
Please, Sign In to add comment