From: http://hi.baidu.com/gmchen/blog/item/780c8202aab75b0b4afb517d.html
分享一道曾經(jīng)的谷歌面試題，覺得特別經(jīng)典。

        題目：對(duì)于一顆完全二叉樹，插入一個(gè)新的節(jié)點(diǎn)。
        struct node
        {
          int data;
            struct node * left;
            struct node * right;
        };
        聲明： insert(struct node * tree, struct node new_node);

        由于是一顆完全二叉樹，所以插入的順序可以參考圖示，插入了節(jié)點(diǎn)4，之后應(yīng)該是節(jié)點(diǎn)5。

        拿到題目第一反應(yīng)就是按層便利，用bfs的就可以搞定，效率在O(n)，實(shí)現(xiàn)起來也簡單，用一個(gè)隊(duì)列就可以完成，這里不多說了。
        當(dāng)時(shí)考官并不滿意，于是就有了第二種解法（提示下），試想下如何比O(n)更快呢？ 那么就往logn上去考慮了，很自然的想到了二分查找，對(duì)于不同的數(shù)組而言，二分查找就是找中間的那個(gè)點(diǎn)。
        但本題比較特別，因?yàn)槭峭耆鏄?，那么插入的點(diǎn)只能在最下一層。于是我們可以去找最下一層的中間點(diǎn)，找到根的左子樹的最右下的節(jié)點(diǎn)，如果這個(gè)點(diǎn)存在，那么說明，最下一層的左邊已經(jīng)填滿，遞歸右子樹，否則遞歸左子樹。
   


        還是用圖例來看會(huì)比較清楚（黃色的點(diǎn)代表當(dāng)前遞歸的根節(jié)點(diǎn)，紅色的點(diǎn)代表左子樹的最右節(jié)點(diǎn)），這里是要插入節(jié)點(diǎn)7，當(dāng)遞歸到5的右子樹時(shí)，可以插入。這個(gè)算法的復(fù)雜度大概在logn到n之間，具體忘記了，有興趣可以推算下。
        總結(jié)：其實(shí)這個(gè)題目的解答太巧了，要在面試中一步到位基本不可能，但是如果可以在面試官的提示下摸到思路，那么已經(jīng)達(dá)到要求了。再就是如果面到這類題目，不妨先把最簡單的bfs方法答上，然后可以在提示下不斷改進(jìn)。