#求二叉树任意节点之间最短路径#acwing3555#北邮

思路：先读取T，进行T次for循环，每次for循环依次读取m、n，维护一个类型为treenode的动态数组。

1.手动将该数组一号位置的parent设置为null（根节点确定）

2.读取n组数据存入left和right，如果不为-1，则将将其根节点孩子指针和其父指针赋值。若为-1则将根节点的孩子指针置为null

建树完成，再进行m次for循环：

1.读取m组数据存入lhs和rhs，根据动态数组向上逐层找父节点，直到临时指针指向null位置，同时将到根节点路径上所有节点的数值压入动态数组

2.对lhs和rhs分别进行上述操作，得到两个动态数组

3。设置两个整形指针变量l,r分别设为数组最后一个元素从后往前遍历，当a.l=0,b.r=0,c.rvec[r]==lvec[l]跳出循环，返回l+r+2即可

/*给定一个 n个结点（编号 1∼n）构成的二叉树，其根结点为 1号点。进行 m次询问，每次询问两个结点之间的最短路径长度。树中所有边长均为 1。
输入格式
第一行包含一个整数 T，表示共有 T组测试数据。每组数据第一行包含两个整数 n,m。接下来 n行，每行包含两个整数，其中第 i行的整数表示结点 i
的子结点编号。如果没有子结点则输出 −1。接下来 m行，每行包含两个整数，表示要询问的两个结点的编号。
输出格式
每组测试数据输出 m行，代表查询的两个结点之间的最短路径长度。
数据范围
1≤T≤10，1≤n,m≤1000*/
#include <cstdio>
#include <vector>

using namespace std;
struct TreeNode{
    int num;
    TreeNode* right;
    TreeNode* left;
    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;
        }

        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 lhs,rhs;
        for(int j=0;j<m;++j){
            scanf("%d%d",&lhs,&rhs);
            vector<int> lvec;
            TreeNode* p=nodeArr[lhs];
            while(p!=NULL){
                lvec.push_back(p->num);
                p=p->parent;
            }
            vector<int> rvec;
            p=nodeArr[rhs];
            while(p!=NULL){
                rvec.push_back(p->num);
                p=p->parent; //把从该节点到根节点的全部路径序列插入完成
            }

            int l=lvec.size()-1;
            int r=rvec.size()-1;
            while(true){
                if(l<0||r<0||lvec[l]!=rvec[r]) {
                    break;
                }
                --l;
                --r;
            }
            printf("%d\n",l+r+2);
        }
    }
    return 0;
}