本文主要是介绍任意一棵二叉树中最大距离的两个节点【算法】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
//后序 求 每个节点最远距离， 倒着遍历， 只遍历了一遍 O( N )
//如果从上往下遍历 则 O( N*N )int GetMaxPathLen( Node* root, int& maxLen ) //maxLen初始值传0
{//别用 全局变量（存在线程安全问题）if ( NULL == root )return 0;int left = GetMaxPathLen( root->_left, maxLen );int right = GetMaxPathLen( root->_right, maxLen );if ( left + right > maxLen )maxLen = left + right;//返回高度return (left>right? left:right) + 1;
}//运行结束后的 maxLen值 就是树中最远的两个节点的距离
//具体的实现方法：
void findMaxLength(Node* root){if(root==NULL) return;//如果左子树为空，则该节点左边最长距离为0 if(root->left==NULL) root->maxLeft=0;//如果右子树为空，则该节点右边最长距离为0 if(root->right==NULL) root->maxRight=0;//如果左子树不为空，递归寻找左边最长距离 if(root->left!=NULL) findMaxLength(root->left);//如果右子树不为空，递归寻找右边最长距离 if(root->right!=NULL) findMaxLength(root->right);//计算左子树最长节点距离 if(root->left!=NULL) {int tempMax=0;if(root->left->maxLeft > root->left->maxRight)tempMax=root->left->maxLeft;else tempMax=root->left->maxRight;root->maxLeft=tempMax+1;}//计算油子树最长节点距离 if(root->right!=NULL) {int tempMax=0;if(root->right->maxLeft > root->right->maxRight)tempMax=root->right->maxLeft;else tempMax=root->right->maxRight;root->maxRight=tempMax+1;}//更新最长距离 if(root->maxLeft+root->maxRight > maxLen)maxLen=root->maxLeft+root->maxRight;
}
这篇关于任意一棵二叉树中最大距离的两个节点【算法】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
