编程之美3.8 求二叉树节点的最大距离

如果我们把二叉树看成一个图，父子节点之间的连线看成是双向的，我们姑且定义“距离”为两个节点之间边的个数。写一个程序求一棵二叉树相距最远的两个节点之间的距离。

 

分析： 对任意一个节点，以该节点为根，假设这个根有k个孩子节点，那么相距最远的两个节点U和V之间的路径与这个根节点的关系有两种情况。

 1.若路径经过根Root，则U和V是属于不同的子树的，且它们都是该子树中到根节点最远的节点，否则跟它们的距离最远相矛盾。

2.若路径不经过Root，那它们一定同属于根的左子树或右子树，并且它们也是该子树中相距最远的两个顶点。

 

因此，问题就可以转化为在子树上的解，从而能够利用动态规划来解决。上代码：

 

 

#include <stdio.h>
#include <stdlib.h>

struct NODE{
	NODE* pLeft;
	NODE* pRight;
	int nMaxLeft; //左子树中的最大深度
	int nMaxRight; //右子树中的最大深度
	char chValue; //该节点的值
};

int nMaxLen = 0;

void FindMaxLen(NODE*  pRoot) {
	if(pRoot == NULL) {
		return;
	}

	if(pRoot->pLeft == NULL) {
		pRoot->nMaxLeft = 0;
	}else {
		FindMaxLen(pRoot->pLeft);
		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) {
		pRoot->nMaxRight = 0;
	}else {
		FindMaxLen(pRoot->pRight);
		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) //最长距离经过root
		nMaxLen = pRoot->nMaxLeft + pRoot->nMaxRight;
}

void createBinaryTree(NODE** pRoot) { //建二叉树
	char c;
	scanf("%c",&c);
	if(c == '#') {
		(*pRoot) = NULL;
	}
	else {
		(*pRoot) = (struct NODE*) malloc(sizeof(struct NODE));
		(*pRoot)->chValue = c;
		createBinaryTree(&((*pRoot)->pLeft));
		createBinaryTree(&((*pRoot)->pRight));
	}
}

void printBinaryTree(NODE* pRoot) { //打印二叉树
	if(pRoot == NULL)
		return;
	printf("%c",pRoot->chValue);
	printBinaryTree(pRoot->pLeft);
	printBinaryTree(pRoot->pRight);
}

int main() {
	struct NODE* root = NULL;
	createBinaryTree(&root);
	printBinaryTree(root);
	FindMaxLen(root);
	printf("\nThe max length is: %d\n",nMaxLen);
	return 0;
}