本文主要是介绍【100题】第三十九题 二叉树任意两个节点间最大距离和有向图割点，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
一，题目（网易有道笔试）
（1）求一个二叉树中任意两个节点间的最大距离，两个节点的距离的定义是这两个节点间边的个数，
比如某个孩子节点和父节点间的距离是1，和相邻兄弟节点间的距离是2，优化时间空间复杂度。
（2）求一个有向连通图的割点，割点的定义是，如果除去此节点和与其相关的边，有向图不再连通，描述算法。
二，分析
（1）解法一：最大距离有两种情况。
一种是：经过根节点，此时只需要求出左右子树的最大深度就可以
另一种：不经过根节点，此时需要递归求解左右子树，然后比较左右子树中最大距离，求大者
#include "stdio.h"#include"stdlib.h" struct NODE{NODE* pLeft; // 左子树NODE* pRight; // 右子树int nMaxLeft; // 左子树中的最长距离int nMaxRight; // 右子树中的最长距离int chValue; // 该节点的值};int nMaxLen = 0;// 寻找树中最长的两段距离void FindMaxLen(NODE* pRoot){// 遍历到叶子节点，返回if(pRoot == NULL)return;// 如果左子树为空，那么该节点的左边最长距离为0if(pRoot -> pLeft == NULL) pRoot -> nMaxLeft = 0;// 如果右子树为空，那么该节点的右边最长距离为0if(pRoot -> pRight == NULL) pRoot -> nMaxRight = 0;// 如果左子树不为空，递归寻找左子树最长距离if(pRoot -> pLeft != NULL) FindMaxLen(pRoot -> pLeft);// 如果右子树不为空，递归寻找右子树最长距离if(pRoot -> pRight != NULL) FindMaxLen(pRoot -> pRight);// 计算左子树最长节点距离if(pRoot -> pLeft != NULL){int nTempMax = 0;if(pRoot -> pLeft -> nMaxLeft > pRoot -> pLeft -> nMaxRight){nTempMax = pRoot -> pLeft -> nMaxLeft;}else{nTempMax = pRoot -> pLeft -> nMaxRight;}pRoot -> nMaxLeft = nTempMax + 1;}// 计算右子树最长节点距离if(pRoot -> pRight != NULL){int nTempMax = 0;if(pRoot -> pRight -> nMaxLeft > pRoot -> pRight -> nMaxRight){nTempMax = pRoot -> pRight -> nMaxLeft;}else{nTempMax = pRoot -> pRight -> nMaxRight;}pRoot -> nMaxRight = nTempMax + 1;}// 更新最长距离if(pRoot -> nMaxLeft + pRoot -> nMaxRight > nMaxLen){nMaxLen = pRoot -> nMaxLeft + pRoot -> nMaxRight;}}NODE *createTree()
{NODE *root;int data;printf("input data:");scanf("%d",&data);//printf("output data:%d\n",data);if(data==0)root=NULL;else/*根左右 前序建立二叉树*/{root=(NODE*)malloc(sizeof(NODE));root->chValue=data;root->pLeft=createTree();root->pRight=createTree(); }return root;
}
int main()
{NODE *root;root=createTree();FindMaxLen(root);printf("%d",nMaxLen);return 0;
}
解法二：采用递归，核心代码
RESULT GetMaximumDistance(NODE* root)
{
if (!root) //当递归到空节点的时候
{
RESULT empty = { 0, -1 }; // trick: nMaxDepth is -1 and then caller will plus 1 to balance it as zero.
return empty;
}
RESULT lhs = GetMaximumDistance(root->pLeft); //左子树递归
RESULT rhs = GetMaximumDistance(root->pRight); //右子树递归
RESULT result;
result.nMaxDepth = max(lhs.nMaxDepth + 1, rhs.nMaxDepth + 1); //求当前节点的最大深度
//这是递归的核心代码：以当前节点为根节点的最大距离为：左右子树距离最大者（不经过根节点）左子树最大节点+右子树最大节点
result.nMaxDistance = max(max(lhs.nMaxDistance, rhs.nMaxDistance), lhs.nMaxDepth + rhs.nMaxDepth + 2);
return result;
}
#include <iostream> using namespace std; struct NODE
{ NODE *pLeft; NODE *pRight;
}; struct RESULT
{ int nMaxDistance; int nMaxDepth;
}; RESULT GetMaximumDistance(NODE* root)
{ if (!root) { RESULT empty = { 0, -1 }; // trick: nMaxDepth is -1 and then caller will plus 1 to balance it as zero. return empty; } RESULT lhs = GetMaximumDistance(root->pLeft); RESULT rhs = GetMaximumDistance(root->pRight); RESULT result; result.nMaxDepth = max(lhs.nMaxDepth + 1, rhs.nMaxDepth + 1); result.nMaxDistance = max(max(lhs.nMaxDistance, rhs.nMaxDistance), lhs.nMaxDepth + rhs.nMaxDepth + 2); return result;
}
void Link(NODE* nodes, int parent, int left, int right)
{ if (left != -1) nodes[parent].pLeft = &nodes[left]; if (right != -1) nodes[parent].pRight = &nodes[right];
} int main()
{ // P. 241 Graph 3-12 NODE test1[9] = { 0 }; Link(test1, 0, 1, 2); Link(test1, 1, 3, 4); Link(test1, 2, 5, 6); Link(test1, 3, 7, -1); Link(test1, 5, -1, 8); cout << "test1: " << GetMaximumDistance(&test1[0]).nMaxDistance << endl; // P. 242 Graph 3-13 left NODE test2[4] = { 0 }; Link(test2, 0, 1, 2); Link(test2, 1, 3, -1); cout << "test2: " << GetMaximumDistance(&test2[0]).nMaxDistance << endl; // P. 242 Graph 3-13 right NODE test3[9] = { 0 }; Link(test3, 0, -1, 1); Link(test3, 1, 2, 3); Link(test3, 2, 4, -1); Link(test3, 3, 5, 6); Link(test3, 4, 7, -1); Link(test3, 5, -1, 8); cout << "test3: " << GetMaximumDistance(&test3[0]).nMaxDistance << endl; // P. 242 Graph 3-14 // Same as Graph 3-2, not test // P. 243 Graph 3-15 NODE test4[9] = { 0 }; Link(test4, 0, 1, 2); Link(test4, 1, 3, 4); Link(test4, 3, 5, 6); Link(test4, 5, 7, -1); Link(test4, 6, -1, 8); cout << "test4: " << GetMaximumDistance(&test4[0]).nMaxDistance << endl;
}（2）求一个有向连通图的割点，割点的定义是，如果除去此节点和与其相关的边，有向图不再连通，描述算法。
最简单的解法：依次删掉一个点和其相连所有边然后判断连通性
在深度优先树中，根结点为割点，当且仅当他有两个或两个以上的子树。
其余结点v为割点，当且仅当存在一个v的后代结点s，s到v的祖先结点之间没有反向边。
记发现时刻dfn(v)为一个节点v在深度优先搜索过程中第一次遇到的时刻。
记标号函数low(v)= min(dfn(v), low(s), dfn(w))
s是v的儿子，(v,w)是反向边。
low(v) 表示从v或v的后代能追溯到的标号最小的节点。
则非根节点v是割点，当且仅当存在v的一个儿子s，low(s) > = dfn(v)
这篇关于【100题】第三十九题 二叉树任意两个节点间最大距离和有向图割点的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
