• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            SEMAN

            曾經(jīng)滄海難為水、除卻巫山不是云

            C++博客 首頁 新隨筆 聯(lián)系 聚合 管理
              9 Posts :: 3 Stories :: 24 Comments :: 0 Trackbacks

                今天參加MS2006年度秋季校園招聘會的筆試第三場,有一個算法題,求一個樹種兩個節(jié)點的最低公共節(jié)點,在網(wǎng)上Google了一下,看到原題大致這樣的:
                  Given the values of two nodes in a *binary search tree*, write a c program to find the lowest common ancestor. You may assume that both values already exist in the tree.

            The function prototype is as follows: int FindLowestCommonAncestor(node* root,int value1,int value)
                       20
                      /  \
                     8    22
                   /   \
                  4     12
                       /  \
                     10    14
                構(gòu)筑函數(shù): struct TreeNode * FindLowestCommonTreeNode(struct node *pNode,)

            Struct TreeNode
            {
               int Data;
               TreeNode *pLeft, *pRight;
            }

            FindLowestAncestor(Struct TreeNode *pRoot, Struct TreeNode *pNode1, Struct TreeNode *pNode2)
            {
               if (pRoot==NULL) 
                  return NULL;
               if (pRoot==pNode1 && pRoot==pNode2) 
                  return pRoot;
               Struct TreeNode *pTemp;
               if (pTemp = FindLowestAncestor(pRoot->pLeft,pNode1,pNode2)) 
                  return pTemp;
               if (pTemp = FindLowestAncestor(pRoot->pRight,pNode1,pNode2)) 
                  return pTemp;
               if (FindLowestAncestor(pRoot,pNode1,pNode1) && FindLowestAncestor(pRoot,pNo
            de2,pNode2)) return pRoot;

               return NULL;
            }

            posted on 2005-11-14 02:05 味全每日C++ 閱讀(1346) 評論(5)  編輯 收藏 引用

            Feedback

            # re: MS的筆試題目 2006-10-22 17:18 小小
            更多試題,請訪問: www.pghome.net/art.html  回復(fù)  更多評論
              

            # re: MS的筆試題目 2006-12-28 23:23 kgha
            FindLowestAncestor(Struct TreeNode *pRoot, Struct TreeNode *pNode1, Struct TreeNode *pNode2)
            {
            if (pRoot==NULL)
            return NULL;
            if (pRoot==pNode1 && pRoot==pNode2)
            return pRoot;
            Struct TreeNode *pTemp;
            if (pTemp = FindLowestAncestor(pRoot->pLeft,pNode1,pNode2))
            return pTemp;
            if (pTemp = FindLowestAncestor(pRoot->pRight,pNode1,pNode2))
            return pTemp;
            if (FindLowestAncestor(pRoot,pNode1,pNode1) && FindLowestAncestor(pRoot,pNo
            de2,pNode2)) return pRoot;

            return NULL;
            }

              回復(fù)  更多評論
              

            # re: MS的筆試題目 2006-12-28 23:37 kgha

            這樣太費解了,不如寫兩個函數(shù)直觀:
            FindLowestAncestor(Struct TreeNode *pRoot, Struct TreeNode *pNode1, Struct TreeNode *pNode2)
            {
            if (pRoot==NULL)
            return NULL;
            if (pRoot==pNode1 && pRoot==pNode2)
            return pRoot;
            Struct TreeNode *pTemp;
            if (pTemp = FindLowestAncestor(pRoot->pLeft,pNode1,pNode2))
            return pTemp;
            if (pTemp = FindLowestAncestor(pRoot->pRight,pNode1,pNode2))
            return pTemp;
            if (FindNode(pRoot,pNode1) && FindLowestAncestor(pRoot,pNo
            de2)) return pRoot;
            return NULL;
            }
            struct TreeNode * FindNode(Struct TreeNode *pRoot, Struct TreeNode *pNode)
            {
            if(pNode在pRoot下)
            {
            return pRoot;
            }
            return NULL;
            }
            因為最后一步僅僅是在pRoot下是否存在pNode1和pNode2,所以還有優(yōu)化的余地  回復(fù)  更多評論
              

            # re: MS的筆試題目 2006-12-28 23:41 kgha
            這樣太費解了,不如寫兩個函數(shù)直觀:
            FindLowestAncestor(Struct TreeNode *pRoot, Struct TreeNode *pNode1, Struct TreeNode *pNode2)
            {
            if (pRoot==NULL)
            return NULL;
            if (pRoot==pNode1 && pRoot==pNode2)
            return pRoot;
            Struct TreeNode *pTemp;
            if (pTemp = FindLowestAncestor(pRoot->pLeft,pNode1,pNode2))
            return pTemp;
            if (pTemp = FindLowestAncestor(pRoot->pRight,pNode1,pNode2))
            return pTemp;
            if (FindNode(pRoot,pNode1) && FindNode(pRoot,pNo
            de2)) return pRoot;
            return NULL;
            }
            struct TreeNode * FindNode(Struct TreeNode *pRoot, Struct TreeNode *pNode)
            {
            if(pNode在pRoot下)
            {
            return pRoot;
            }
            return NULL;
            }
            因為最后一步僅僅是在pRoot下是否存在pNode1和pNode2,所以還有優(yōu)化的余地
            上面的有點小錯誤,呵呵  回復(fù)  更多評論
              

            # re: MS的筆試題目 2008-03-07 17:31 521zheng
            其實沒有這么麻煩的,
            考慮一下二叉查找樹的特點,如果兩個節(jié)點的值都大于或都小于某一個節(jié)點的值,就繼續(xù)遍歷下去,否則返回節(jié)點的值
            int FindLowesCommonNode(root * node , int a, int b)
            {
            if(a<=node.value && b<=node.value)
            return FindLowesCommonNode(node->left, a,b);
            if(a>=node.value && b>=node.value)
            return FindLowesCommonNode(node->right, a,b);
            return root.value;
            }  回復(fù)  更多評論
              


            只有注冊用戶登錄后才能發(fā)表評論。
            網(wǎng)站導(dǎo)航: 博客園   IT新聞   BlogJava   博問   Chat2DB   管理


            亚洲伊人久久大香线蕉综合图片| 99久久免费国产精品| 久久久久亚洲精品日久生情| 久久亚洲精品成人无码网站| 欧美熟妇另类久久久久久不卡 | 亚洲av成人无码久久精品| 亚洲伊人久久大香线蕉综合图片| 99久久99这里只有免费费精品 | 一本久久a久久精品综合香蕉| 无码人妻久久一区二区三区蜜桃| 亚洲中文精品久久久久久不卡| 99久久精品九九亚洲精品| 三级片免费观看久久| 午夜天堂av天堂久久久| 久久99精品久久久久久噜噜| 亚洲国产欧美国产综合久久 | 欧美黑人激情性久久| 国产精品一区二区久久精品无码| 免费久久人人爽人人爽av| 国产免费福利体检区久久 | 亚洲AV日韩精品久久久久| 岛国搬运www久久| 久久99久久99小草精品免视看| 日韩欧美亚洲综合久久 | 色欲久久久天天天综合网精品| 久久精品国产亚洲Aⅴ香蕉 | 国内精品伊人久久久久| 久久精品日日躁夜夜躁欧美| 久久精品中文字幕第23页| 99久久精品国产高清一区二区| 狠狠色噜噜色狠狠狠综合久久| 狠狠色丁香婷婷综合久久来来去| 97久久精品无码一区二区| 日日狠狠久久偷偷色综合0| 香港aa三级久久三级| 国产一级做a爰片久久毛片| 久久不见久久见免费视频7| 性做久久久久久久| 麻豆亚洲AV永久无码精品久久| 久久国产欧美日韩精品| 伊人久久大香线蕉av一区|