生活随笔
收集整理的這篇文章主要介紹了
微软100题第11题
小編覺(jué)得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.
參照：http://blog.csdn.net/caryaliu/article/details/8107089
參照：http://blog.csdn.net/lalor/article/details/7626678
把二叉樹(shù)看成一個(gè)圖，父子節(jié)點(diǎn)之間的連線看成是雙向的，我們姑且定義"距離"為兩個(gè)節(jié)點(diǎn)之間的個(gè)數(shù)。
寫(xiě)一個(gè)程序求一棵二叉樹(shù)中相距最遠(yuǎn)的兩個(gè)節(jié)點(diǎn)之間的距離。
如下圖所示，粗箭頭的邊表示最長(zhǎng)距離：
樹(shù)中相距最遠(yuǎn)的兩個(gè)節(jié)點(diǎn)是A, B
分析可知：對(duì)于二叉樹(shù)，若要兩個(gè)節(jié)點(diǎn)U，V相距最遠(yuǎn)，有兩種情況：
1，從U節(jié)點(diǎn)到V節(jié)點(diǎn)之間的路徑經(jīng)過(guò)根節(jié)點(diǎn)
2，從U節(jié)點(diǎn)到V節(jié)點(diǎn)之間的路徑不經(jīng)過(guò)根節(jié)點(diǎn)，這種情況下，U，V節(jié)點(diǎn)必定在根節(jié)點(diǎn)的左子樹(shù)或者右子樹(shù)上，這樣就轉(zhuǎn)化為求以根節(jié)點(diǎn)的孩子節(jié)點(diǎn)為根節(jié)點(diǎn)的二叉樹(shù)中最遠(yuǎn)的兩個(gè)節(jié)點(diǎn)間的距離
上面所說(shuō)的經(jīng)過(guò)根節(jié)點(diǎn)，是指路徑中包含根節(jié)點(diǎn)，例如：加入上圖中只有左子樹(shù)FGHA, 那么最長(zhǎng)距離的兩個(gè)節(jié)點(diǎn)是F, A，該路徑中包含根節(jié)點(diǎn)F，也稱(chēng)為經(jīng)過(guò)根節(jié)點(diǎn)。
于是我們可以遞歸求解，按照二叉樹(shù)的中序遍歷方式遍歷二叉樹(shù)，在遍歷的過(guò)程中尋找相距最遠(yuǎn)的兩個(gè)節(jié)點(diǎn)。
解法1：
#include?<iostream>?? #include?<stdlib.h>?? using?namespace?std;?? ?? struct?BinaryTreeNode??? {?? ????int?m_nValue;?? ????struct?BinaryTreeNode?*m_pLeft;?? ????struct?BinaryTreeNode?*m_pRight;?? };?? ?? int?maxDistance(BinaryTreeNode?*root,?int?*max);?? int?DistanceCore(BinaryTreeNode?*root,int?*max);?? ?? void?Traverse(?BinaryTreeNode?*?root);?? BinaryTreeNode*?Construct(int?*preorder,?int?*inorder,?int?lenght);?? BinaryTreeNode*?ConstructCore(int?*startPreorder,?int?*endPreorder,?int?*startInorder,?int?*endInorder);?? int?InsertNodeAtMostRight(BinaryTreeNode?*?root,?BinaryTreeNode?*?node);?? ?? ?? int?main(int?argc,?char*?argv[])?? {?? ?? ????int?preOrder[]?=?{5,?4,?8,?9,?6,?3,?18,?19,?2};?? ????int?inOrder[]?=?{9,?8,?6,?3,?4,?5,?19,?18,?2};?? ?? ????int?max;?? ?? ?????? ????BinaryTreeNode?*parent?=?Construct(preOrder,?inOrder,?sizeof(inOrder)?/?sizeof(inOrder[0]));?? ?? ????cout?<<?"A樹(shù)的后序遍歷的結(jié)果："?<<?endl;?? ????Traverse(parent);?? ????cout?<<?endl;?? ?? ????BinaryTreeNode?*node1?=?(BinaryTreeNode?*)malloc(sizeof(BinaryTreeNode));?? ????BinaryTreeNode?*node2?=?(BinaryTreeNode?*)malloc(sizeof(BinaryTreeNode));?? ?? ????node1->m_nValue?=?0;?? ????node1->m_pLeft?=?NULL;?? ????node1->m_pRight?=?NULL;?? ?? ????node2->m_nValue?=?0;?? ????node2->m_pLeft?=?NULL;?? ????node2->m_pRight?=?NULL;?? ?? ????maxDistance(parent,?&max);?? ????cout?<<"max?distance?of?tree's?nodes?:?"?<<?max?<<?endl;?? ?? ????InsertNodeAtMostRight(parent,?node1);?? ????maxDistance(parent,?&max);?? ????cout?<<"max?distance?of?tree's?nodes?after?insert?node1:?"?<<?max?<<?endl;?? ?? ????InsertNodeAtMostRight(parent,?node2);?? ????maxDistance(parent,?&max);?? ????cout?<<"max?distance?of?tree's?nodes?after?insert?node2:?"?<<?max?<<?endl;?? ?? ?????? ????maxDistance(node2,?&max);?? ????cout?<<"just?one?node?"?<<?max?<<?endl;?? ?? ?????? ????maxDistance(node1,?&max);?? ????cout?<<"just?two?node?"?<<?max?<<?endl;?? ????return?0;?? }?? ?? BinaryTreeNode*?Construct(int?*preorder,?int?*inorder,?int?lenght)?? {?? ????if?(preorder?==?NULL?||?inorder?==?NULL?||?lenght?<=?0)??? ????{?? ????????return?NULL;?? ????}?? ????return?ConstructCore(preorder,?preorder?+?lenght?-?1,?inorder,?inorder?+?lenght?-?1);?? }?? ?? BinaryTreeNode*?ConstructCore(int?*startPreorder,?int?*endPreorder,?int?*startInorder,?int?*endInorder)?? {?? ????int?rootValue?=?startPreorder[0];?? ????BinaryTreeNode?*root?=?new?BinaryTreeNode();?? ????root->m_nValue?=?rootValue;?? ????root->m_pLeft?=?root->m_pRight?=?NULL;?? ?? ????if?(startPreorder?==?endPreorder)??? ????{?? ????????if?(startInorder?==?endInorder?&&?*startPreorder?==?*startInorder)??? ????????{?? ????????????return?root;?? ????????}?? ????????else?? ????????{?? ????????????cout?<<?"Invalid?input"?<<?endl;?? ????????????exit(-1);?? ????????}?? ????}?? ?? ????int?*rootInorder?=?startInorder;?? ????while?(rootInorder?<=?endInorder?&&?*rootInorder?!=?rootValue)??? ????{?? ????????++rootInorder;?? ????}?? ????if?(rootInorder?<=?endInorder?&&?*rootInorder?!=?rootValue)??? ????{?? ????????cout?<<?"Invalid?input"?<<?endl;?? ????????exit(-1);?? ????}?? ?? ????int?leftLength?=?rootInorder?-?startInorder;?? ????int?*leftPreorderEnd?=?startPreorder?+?leftLength;?? ?? ????if?(leftLength?>?0)??? ????{?? ????????root->m_pLeft?=?ConstructCore(startPreorder?+?1,?leftPreorderEnd,?startInorder,?rootInorder?-?1);?? ????}?? ????if?(leftLength?<?endPreorder?-?startPreorder)??? ????{?? ????????root->m_pRight?=?ConstructCore(leftPreorderEnd?+?1,?endPreorder,?rootInorder?+?1,?endInorder);?? ????}?? ?? ????return?root;?????? }?? ?? void?Traverse(?BinaryTreeNode?*?root)?? {?? ????if?(root?==?NULL)??? ????{?? ????????return;?? ????}?? ????else?? ????{?? ????????Traverse(root->m_pLeft);?? ????????Traverse(root->m_pRight);?? ????????cout?<<?root->m_nValue?<<?"??";?? ????}?? }?? int?maxDistance(BinaryTreeNode?*root,?int?*max)?? {?? ?????? ????if?(root?==?NULL?||?max?==?NULL)??? ????{?? ????????return?-1;?? ????}?? ????*max?=?0;?? ????return?DistanceCore(root,?max);?? }?? ?? int?DistanceCore(BinaryTreeNode?*root,?int?*max)?? {?? ?????? ????if?(root->m_pLeft?==?NULL?&&?root->m_pRight?==?NULL)??? ????{?? ????????return?0;?? ????}?? ?? ?????? ????int?lDistance?=?0;?? ????int?rDistance?=?0;?? ?? ?????? ????if?(root->m_pLeft?!=?NULL)??? ????{?? ????????lDistance?=?1?+?DistanceCore(root->m_pLeft,?max);?? ????}?? ?? ????if?(root->m_pRight?!=?NULL)??? ????{?? ????????rDistance?=?1?+?DistanceCore(root->m_pRight,?max);?? ????}?? ?? ?????? ????if?(lDistance?+?rDistance?>?*max)??? ????{?? ?????????? ????????*max?=?lDistance?+?rDistance;?? ????}?? ?????? ????return?lDistance?>?rDistance???lDistance?:?rDistance;?? }?? ?? ?? ?? int?InsertNodeAtMostRight(BinaryTreeNode?*?root,?BinaryTreeNode?*?node)?? {?? ????if?(root?==?NULL?||?node?==?NULL)??? ????{?? ????????return?-1;?? ????}?? ?? ????while?(root->m_pRight?!=?NULL)??? ????{?? ????????root?=?root->m_pRight;?? ????}?? ?? ????root->m_pRight?=?node;?? ????return?0;?? } ? 解法2：
#include?<stdlib.h>?? #include?<stdio.h>?? ?? typedef?struct?Node?{?? ????struct?Node?*pleft;??????? ????struct?Node?*pright;?????? ????char?chValue;????????????? ?? ????int?leftMaxValue;????????? ????int?rightMaxValue;???????? }LNode,?*BinTree;?? ?? void?findMaxLen(BinTree?root,?int?*maxLen)?{?? ?????? ????if(root?==?NULL)?? ????????return;?? ?? ?????? ????if(root->pleft?==?NULL)?? ????????root->leftMaxValue?=?0;?? ?? ?????? ????if(root->pright?==?NULL)?? ????????root->rightMaxValue?=?0;?? ?? ?????? ????if(root->pleft?!=?NULL)?? ????????findMaxLen(root->pleft,?maxLen);?? ?? ?????? ????if(root->pright?!=?NULL)?? ????????findMaxLen(root->pright,?maxLen);?? ?? ?????? ????if(root->pleft?!=?NULL)?{?? ????????if(root->pleft->leftMaxValue?>?root->pleft->rightMaxValue)?? ????????????root->leftMaxValue?=?root->pleft->leftMaxValue?+?1;?? ????????else?? ????????????root->leftMaxValue?=?root->pleft->rightMaxValue?+?1;?? ????}?? ?? ?????? ????if(root->pright?!=?NULL)?{?? ????????if(root->pright->leftMaxValue?>?root->pright->rightMaxValue)?? ????????????root->rightMaxValue?=?root->pright->leftMaxValue?+?1;?? ????????else?? ????????????root->rightMaxValue?=?root->pright->rightMaxValue?+?1;?? ????}?? ?? ?????? ????if(root->leftMaxValue?+?root->rightMaxValue?>?*maxLen)?? ????????*maxLen?=?root->leftMaxValue?+?root->rightMaxValue;?? }?? ?? ?? void?buildBinTree(BinTree?*root)?? {?? ????char?ch;?? ????scanf("%c",?&ch);?????? ????fpurge(stdin);?? ????if(ch?==?'?')?????????? ????????*root?=?NULL;?? ????else?{????????????????? ????????*root?=?(BinTree)malloc(sizeof(LNode));?? ????????(*root)->chValue?=?ch;?? ????????(*root)->leftMaxValue?=?0;?? ????????(*root)->rightMaxValue?=?0;?? ?? ????????buildBinTree(&(*root)->pleft);?? ????????buildBinTree(&(*root)->pright);?? ????}?? }?? ?? ?? void?destroyBinTree(BinTree?*root)?? {?? ????if(*root?!=?NULL)?{?? ????????destroyBinTree(&(*root)->pleft);?? ????????destroyBinTree(&(*root)->pright);?? ?? ????????free(*root);?? ????????*root?=?NULL;?? ????}?? }?? ?? ?? void?preOrderTraverse(BinTree?root)?? {?? ????if(root?!=?NULL)?{?? ????????preOrderTraverse(root->pleft);?? ????????printf("%c",?root->chValue);?? ????????preOrderTraverse(root->pright);?? ????}?? }?? ?? int?main()?{?? ????BinTree?root;?? ????buildBinTree(&root);?? ????preOrderTraverse(root);?? ????printf("\n");?? ????int?maxLen?=?0;?? ????findMaxLen(root,?&maxLen);?? ????printf("maxLen?=?%d\n",?maxLen);?? ????destroyBinTree(&root);?? } ?
總結(jié)
以上是生活随笔為你收集整理的微软100题第11题的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。
