题解 | 二叉树任意两点之间最短路径长度

题目描述：

对二叉树，计算任意两个结点的最短路径长度。

输入

第一行输入测试数据组数T

第二行输入n,m 。n代表结点的个数，m代表要查询的数据组数

接下来n行，每行输入两个数，代表1~n结点的孩子结点，如果没有孩子结点则输入-1.根节点为1.

接下来m行，每行输入两个数，代表要查询的两个结点

输出

每组测试数据输出m行，代表查询的两个结点之间的最短路径长度

测试样例：

输入

1

8 4

2 3

4 5

6 -1

-1 -1

-1 7

-1 -1

8 -1

-1 -1

1 6

4 6

4 5

8 1

输出

2

4

2

4

#include<stdio.h>
#include<iostream>
#include<string>
#include<vector>
using namespace std;

struct TreeNode {
	int num;
	TreeNode* left;
	TreeNode* right;
	TreeNode* parent;//方便找到父结点
};
int main() {
	int t;
	scanf("%d", &t);
	for (int i = 0; i < t; i++) {
		int n, m;
		scanf("%d%d", &n, &m);
		vector<TreeNode*> nodeArr(n + 1);//用动态数组保存树
		//建树
		for (int j = 1; j <= n; j++) {
			nodeArr[j] = new TreeNode;
			nodeArr[j]->num = j;//建树1——n编号
		}
		//添加父结点信息
		nodeArr[1]->parent = NULL;
		for (int j = 1; j <=n; j++) {
			int left, right;
			scanf("%d%d", &left, &right);
			if (left != -1) {
				nodeArr[j]->left = nodeArr[left];
				nodeArr[left]->parent = nodeArr[j];
			}
			else {
				nodeArr[j]->left = NULL;
			}
			if (right != -1) {
				nodeArr[j]->right = nodeArr[right];
				nodeArr[right]->parent = nodeArr[j];
			}
			else {
				nodeArr[j]->right = NULL;
			}
		}
		int L, R;

		for (int j = 0; j < m; ++j) {
			//保存L和R的分别到根结点的路径，用动态数组
			scanf("%d%d", &L, &R);
			vector<int> Lvec;
			TreeNode* p = nodeArr[L];//从当前结点开始
			while (p != NULL) {
				Lvec.push_back(p->num);
				p = p->parent;
			}
			vector<int> Rvec;
			p = nodeArr[R];//从当前结点开始
			while (p != NULL) {
				Rvec.push_back(p->num);
				p = p->parent;
			}

			//找到两条路径的交点的前一个结点下标
			int Llen = Lvec.size() - 1;
			int Rlen = Rvec.size() - 1;
			while (true) {
				if (Llen < 0 || Rlen < 0 || Lvec[Llen] != Rvec[Rlen]) {
					break;//下面开始没有交点了退出
				}
				--Llen;
				--Rlen;
			}
			printf("%d\n", Llen + Rlen + 2);

		}
	}

	return 0;
}