php - Binary Tree Maximum Difference of Labels
问题描述
I have the below question, but I'm having a hard time making sense of it and implementing it in PHP.
You have a binary tree with N nodes (1 <= N <= 100000) numbered from 0 to N - 1, each one labeled with some integer. You have to answer Q (1 <= Q <= 75000) queries, each one denoted by some node (some integer between 0 and N – 1).
The answer for each query is the largest difference between the labels you find in the path from the given node to the root of the tree, which will always be node 0. N will be given in the first line of the input. N lines follow the i-th line describes the data of the i-th node of the tree (the first line describes node 0, and so on), with 3 integers: label, left child, right child. The absence of any of the children will be denoted by -1. Then a line with the integer Q, followed by Q lines, each one a single query as described above.
Case 1:
For the input provided as follows:
3
10 1 2
12 -1 -1
15 -1 -1
2
1
2
The output of the program will be:
2
5
Case 2:
For the input provided as follows:
3
10 1 -1
15 2 -1
20 -1 -1
2
1
2
The output of the program will be:
5
10
Getting that maximum difference, for example for case 2,
I'd say output for query two would be 5 because from the data my binary tree has 10(root), then node 15 to the left of the root, then node 20 to the left of 15, so 20-15 is same as 15-10, which makes them both 5. Am I not understanding something here or what ... Any insights are welcome.
解决方案
考虑根节点和给定节点之间的所有节点
对于如下提供的输入：
3
10 1 -1
15 2 -1
20 -1 -1
1
2
该程序的输出将是：
10
你得到10-15-20了你应该走的路
max(10,15,20) - min(10,15,20) => 10
对于如下提供的输入：
7
33 1 5
11 2 -1
27 3 6
87 4 -1
3 -1 -1
666 -1 -1
6666 -1 -1
1
4
该程序的输出将是：
84
33-11-27-87-3你得到更长的链条
max(33,11,27,87,3) - min(33,11,27,87,3) => 87-3 => 84