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

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

#inlcude <iostream>

using namespace std;

struct Node

{

Node *lchild;

Node *rchild;

//data

};

//因为最大距离，一定是已树中某点为根　的左右子树高度之和

int get_max_distance(tree* root,int& maxlen)

{

if(root==null) return 0;//空结点返回0

int Lhight = get_max_distance(root->lchild, maxlen);

int Rhight = get_max_distance(root->rchild, maxlen) ;

if( Lhight+Rhight > maxlen) maxlen = Lhight+Rhight ;

return max(Lhight,Rhight)+1; //树的高度＝max(左子树高度，右子树高度)+1

}

01 // 数据结构定义

02 struct NODE

03 {

04 NODE* pLeft; // 左子树

05 NODE* pRight; // 右子树

06 int nMaxLeft; // 左子树中的最长距离

07 int nMaxRight; // 右子树中的最长距离

08 char chValue; // 该节点的值

09 };

10

11 int nMaxLen = 0;

12

13 // 寻找树中最长的两段距离

14 void FindMaxLen(NODE* pRoot)

15 {

16 // 遍历到叶子节点，返回

17 if(pRoot == NULL)

18 {

19 return;

20 }

21

22 // 如果左子树为空，那么该节点的左边最长距离为0

23 if(pRoot -> pLeft == NULL)

24 {

25 pRoot -> nMaxLeft = 0;

26 }

27

28 // 如果右子树为空，那么该节点的右边最长距离为0

29 if(pRoot -> pRight == NULL)

30 {

31 pRoot -> nMaxRight = 0;

32 }

33

34 // 如果左子树不为空，递归寻找左子树最长距离

35 if(pRoot -> pLeft != NULL)

36 {

37 FindMaxLen(pRoot -> pLeft);

38 }

39

40 // 如果右子树不为空，递归寻找右子树最长距离

41 if(pRoot -> pRight != NULL)

42 {

43 FindMaxLen(pRoot -> pRight);

44 }

45

46 // 计算左子树最长节点距离

47 if(pRoot -> pLeft != NULL)

48 {

49 int nTempMax = 0;

50 if(pRoot -> pLeft -> nMaxLeft > pRoot -> pLeft -> nMaxRight)

51 {

52 nTempMax = pRoot -> pLeft -> nMaxLeft;

53 }

54 else

55 {

56 nTempMax = pRoot -> pLeft -> nMaxRight;

57 }

58 pRoot -> nMaxLeft = nTempMax + 1;

59 }

60

61 // 计算右子树最长节点距离

62 if(pRoot -> pRight != NULL)

63 {

64 int nTempMax = 0;

65 if(pRoot -> pRight -> nMaxLeft > pRoot -> pRight -> nMaxRight)

66 {

67 nTempMax = pRoot -> pRight -> nMaxLeft;

68 }

69 else

70 {

71 nTempMax = pRoot -> pRight -> nMaxRight;

72 }

73 pRoot -> nMaxRight = nTempMax + 1;

74 }

75

76 // 更新最长距离

77 if(pRoot -> nMaxLeft + pRoot -> nMaxRight > nMaxLen)

78 {

79 nMaxLen = pRoot -> nMaxLeft + pRoot -> nMaxRight;

80 }

81 }