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

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

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

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


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