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

            曾經滄海難為水、除卻巫山不是云

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

                今天參加MS2006年度秋季校園招聘會的筆試第三場,有一個算法題,求一個樹種兩個節點的最低公共節點,在網上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
                構筑函數: 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  回復  更多評論
              

            # 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;
            }

              回復  更多評論
              

            # re: MS的筆試題目 2006-12-28 23:37 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 (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,所以還有優化的余地  回復  更多評論
              

            # re: MS的筆試題目 2006-12-28 23:41 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 (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,所以還有優化的余地
            上面的有點小錯誤,呵呵  回復  更多評論
              

            # re: MS的筆試題目 2008-03-07 17:31 521zheng
            其實沒有這么麻煩的,
            考慮一下二叉查找樹的特點,如果兩個節點的值都大于或都小于某一個節點的值,就繼續遍歷下去,否則返回節點的值
            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;
            }  回復  更多評論
              

            久久精品国产亚洲欧美| 久久亚洲精品中文字幕三区| 久久精品女人天堂AV麻| 国产亚洲成人久久| 一级女性全黄久久生活片免费 | 久久夜色精品国产噜噜噜亚洲AV| 国产精品美女久久久久网| 亚洲国产精品久久| 久久久久久久女国产乱让韩| 国内高清久久久久久| 久久久久夜夜夜精品国产| 怡红院日本一道日本久久 | 色诱久久久久综合网ywww| 99久久99这里只有免费费精品| Xx性欧美肥妇精品久久久久久| 久久只有这里有精品4| 久久无码人妻一区二区三区 | 日韩欧美亚洲综合久久影院Ds| 久久午夜伦鲁片免费无码| 色综合久久久久网| 日本人妻丰满熟妇久久久久久| 久久久久久毛片免费看| 久久综合综合久久综合| 久久黄色视频| 久久精品草草草| 久久综合久久自在自线精品自| 精品伊人久久久| 日本免费久久久久久久网站| 一本久久a久久精品vr综合| 久久久久99精品成人片牛牛影视| 久久免费高清视频| 久久亚洲精品成人av无码网站| 亚洲国产精品狼友中文久久久| 国产69精品久久久久99尤物| 久久亚洲精品国产精品| 久久久久久久精品妇女99| 久久精品一区二区影院| 精品99久久aaa一级毛片| 日韩一区二区久久久久久 | 久久天天躁狠狠躁夜夜2020老熟妇| 精品免费tv久久久久久久|