哪里有做ppt模板下载网站,保定企业网站建设,淘客必须做网站,天津搜索引擎优化求一个二叉树中任意两个节点间的最大距离#xff0c;两个节点的距离的定义是这两个节点间边的个数#xff0c; 比如某个孩子节点和父节点间的距离是1#xff0c;和相邻兄弟节点间的距离是2#xff0c;优化时间空间复杂度。 一种是#xff1a;经过根节点#xff0c;此时只…求一个二叉树中任意两个节点间的最大距离两个节点的距离的定义是这两个节点间边的个数 比如某个孩子节点和父节点间的距离是1和相邻兄弟节点间的距离是2优化时间空间复杂度。 一种是经过根节点此时只需要求出左右子树的最大深度就可以 另一种不经过根节点此时需要递归求解左右子树然后比较左右子树中最大距离求大者 1 #include stdio.h2 #includestdlib.h 3 struct NODE4 {5 NODE* pLeft; // 左子树6 NODE* pRight; // 右子树7 int nMaxLeft; // 左子树中的最长距离8 int nMaxRight; // 右子树中的最长距离9 int chValue; // 该节点的值10 };11 12 int nMaxLen 0;13 14 // 寻找树中最长的两段距离15 void FindMaxLen(NODE* pRoot)16 {17 // 遍历到叶子节点返回18 if(pRoot NULL)19 return;20 21 // 如果左子树为空那么该节点的左边最长距离为022 if(pRoot - pLeft NULL) 23 pRoot - nMaxLeft 0;24 25 26 // 如果右子树为空那么该节点的右边最长距离为027 if(pRoot - pRight NULL) 28 pRoot - nMaxRight 0;29 30 31 // 如果左子树不为空递归寻找左子树最长距离32 if(pRoot - pLeft ! NULL) 33 FindMaxLen(pRoot - pLeft);34 35 36 // 如果右子树不为空递归寻找右子树最长距离37 if(pRoot - pRight ! NULL) 38 FindMaxLen(pRoot - pRight);39 40 41 // 计算左子树最长节点距离42 if(pRoot - pLeft ! NULL)43 {44 int nTempMax 0;45 if(pRoot - pLeft - nMaxLeft pRoot - pLeft - nMaxRight)46 {47 nTempMax pRoot - pLeft - nMaxLeft;48 }49 else50 {51 nTempMax pRoot - pLeft - nMaxRight;52 }53 pRoot - nMaxLeft nTempMax 1;54 }55 56 // 计算右子树最长节点距离57 if(pRoot - pRight ! NULL)58 {59 int nTempMax 0;60 if(pRoot - pRight - nMaxLeft pRoot - pRight - nMaxRight)61 {62 nTempMax pRoot - pRight - nMaxLeft;63 }64 else65 {66 nTempMax pRoot - pRight - nMaxRight;67 }68 pRoot - nMaxRight nTempMax 1;69 }70 71 // 更新最长距离72 if(pRoot - nMaxLeft pRoot - nMaxRight nMaxLen)73 {74 nMaxLen pRoot - nMaxLeft pRoot - nMaxRight;75 }76 }77 78 NODE *createTree()79 {80 NODE *root;81 int data;82 printf(input data:);83 scanf(%d,data);84 //printf(output data:%d\n,data);85 86 if(data0)87 rootNULL;88 else/*根左右 前序建立二叉树*/89 {90 root(NODE*)malloc(sizeof(NODE));91 root-chValuedata;92 root-pLeftcreateTree();93 root-pRightcreateTree(); 94 }95 return root;96 } 97 int main()98 {99 NODE *root;
100 rootcreateTree();
101 FindMaxLen(root);
102
103 printf(%d,nMaxLen);
104 return 0;
105 } 转载于:https://www.cnblogs.com/WayneZeng/archive/2013/04/21/3034187.html
