• <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   管理


            久久精品无码午夜福利理论片| 狠狠色伊人久久精品综合网| 一本色道久久88综合日韩精品 | 无码精品久久一区二区三区| 久久免费观看视频| 看久久久久久a级毛片| 久久综合久久综合九色| 思思久久99热免费精品6| 人妻精品久久久久中文字幕69 | 女人香蕉久久**毛片精品| 精品久久久久中文字幕一区| 99久久免费国产精品特黄| 久久国产精品久久精品国产| 久久精品国产国产精品四凭| 欧美丰满熟妇BBB久久久| 久久国产成人精品国产成人亚洲| 久久精品国产日本波多野结衣| 久久综合九色综合精品| 色88久久久久高潮综合影院| 国产综合成人久久大片91| 午夜精品久久久久久中宇| 久久国产成人午夜aⅴ影院| 久久亚洲AV成人无码电影| 久久精品国产色蜜蜜麻豆| 国产高潮国产高潮久久久| 久久无码AV中文出轨人妻| 久久久国产精品| 99久久久久| 久久夜色精品国产亚洲| 久久久久无码精品国产不卡| 久久综合亚洲鲁鲁五月天| 久久久WWW免费人成精品| 精品水蜜桃久久久久久久| 久久97精品久久久久久久不卡| 久久亚洲私人国产精品vA| 一本久道久久综合狠狠爱| 中文字幕无码久久久| 久久人人爽人人人人爽AV| 欧美一区二区久久精品| 久久天天躁狠狠躁夜夜avapp| 久久人人爽人人爽人人片AV不 |