本文主要是介绍【算法】多叉树寻找A\B节点的分支点，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
小米笔试中的一道题，题意是，多叉树，0为根节点，给定矩阵m，
m[i][j]==1表示两点连接，给出A,B两个节点，寻找他们的最近分支节点。
如题：
"001001";"001100";"110010";"010000";"001000";"100000";0/ \2 5/ \1 4/3给出节点(3, 4)则最近分割点为2.
思路：类似于图的遍历，根据给出连接关系，找到每个节点的父节点，存入数组，对于给出的节点（3,4），依次找出3的父节点路径，然后找出4的路径，两者开始比对，最先相同的点即为分割点。
int h(vector<string>& m, int a, int b)
{if(m.size() == 0)return 0;vector<int> f(m.size(), 0);//表示父节点vector<int> lable(m.size(), 0);//标记是否标注过此点lable[0] = 1;//表示根节点已标记deque<int> note;//要查询的节点note.push_back(0);//从根节点开始int count = 1;//标记过的数目while(!note.empty()){if(count == m.size())break;//表示所有节点的父节点都记录完毕int i = note.front();note.pop_front();for(int j = 0; j < m[i].size();j++){if(m[i][j] == '1'){if(lable[j] == 0){//表示找到当前节点的子节点，同时该节点未标记过count++;f[j] = i;lable[j] = 1;note.push_back(j);//将其子节点加入队列}}}}set<int> ip;//记录a节点的路径ip.insert(a);int ma = f[a];while(ma != 0){//未到根节点ip.insert(ma);ma = f[ma];}int mb = b;while(mb != 0){if(ip.count(mb))return mb;//若找到与a相同的节点即返回mb = f[mb];}return 0;
}
这篇关于【算法】多叉树寻找A\B节点的分支点的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
