查找二叉树最远两个节点的距离

my_acm

于 2015-06-27 22:47:34 发布

阅读量1.5k

点赞数

分类专栏：二叉树

本文链接：https://blog.csdn.net/my_acm/article/details/46664877

版权

二叉树专栏收录该内容

1 篇文章

订阅专栏

本文介绍了一种算法用于在二叉树中找到距离最远的两个节点，并更新最大距离。通过递归遍历树的左右子节点，计算每个节点到最近祖先节点的距离，最终找出最大距离。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

struct Node{
	Node * left;
	Node * right;
	int lmaxlen;
	int rmaxlen;
	char val;
};

int maxlen = 0;

//查找二叉树中最远的两个节点
void search(Node * root){
	if(root == NULL){
		return ;
	}
	if(root->left != NULL){
		search(root->left);
	}else{
		root->lmaxlen = 0;
	}
	if(root->right != NULL){
		search(root->right);
	}else{
		root->rmaxnlen = 0;
	}
	if(root->left != NULL){
		int tpmaxlen = 0;
		if(root->left->lmaxlen > root->left->rmaxlen){
			tpmaxlen = root->left->lmaxlen;
		}else{
			tpmaxlen = root->left->raxlen;
		}
		root->lmaxlen = tpmaxlen + 1;
	}
	if(root->right != NULL{
		int tpmaxlen = 0;
		if(root->right->rmaxlen > root->right->lmaxlen){
			tpmaxlen = root->right->rmaxlen;	
		}else{
			tpmaxlen = root->right->lmaxlen;
		}
		root->lmaxlen = tpmaxlen + 1;
	}
	if(root->lmaxlen + root->rmaxlen > maxlen){
		maxlen = root->lmaxlen + root->rmaxlen;
	}	
}