題記：寫這篇博客要主是加深自己對按層空間復(fù)雜度的認(rèn)識和總結(jié)實現(xiàn)算法時的一些驗經(jīng)和訓(xùn)教，如果有錯誤請指出，萬分感謝。

????

Follow up for problem " Populating Next Right Pointers in Each Node ".

????

What if the given tree could be any binary tree? Would your previous solution still work?

????

Note:? You may only use constant extra space.

????

?

????

For example,
Given the following binary tree,

    1

       /  \

      2    3

     / \    \

    4   5    7
  

????

?

????

After calling your function, the tree should look like:

    1 -> NULL

       /  \

      2 -> 3 -> NULL

     / \    \

    4-> 5 -> 7 -> NULL
  

????碼好一次性通過~~ yeah~

????路思是很明顯的，一層一層的找，利用前當(dāng)層的next來figure out下一層的next

????第一次做的時候用了queue來實現(xiàn)的按層遍歷，此次才看到了 O(1)的空間復(fù)雜度。

????從新寫了一下，為了看起來路思清楚點，碼代寫的略長。

    /**

 * Definition for binary tree with next pointer.

 * struct TreeLinkNode {

 *  int val;

 *  TreeLinkNode *left, *right, *next;

 *  TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}

 * };

 */

class Solution {

public:

    TreeLinkNode* myNextLine(TreeLinkNode *cur){

        if(cur -> left) return cur -> left;

        if(cur -> right) return cur -> right;

        

        while(cur -> next){

            cur = cur -> next;

            if(cur -> left) return cur -> left;

            if(cur -> right) return cur -> right;

        }

        

        return NULL;

    }



    TreeLinkNode* myleftnext(TreeLinkNode *cur){

        if(cur -> right) return cur -> right;

        

        while(cur -> next){

            cur = cur -> next;

            if(cur -> left) return cur -> left;

            if(cur -> right) return cur -> right;

        }

        

        return NULL;

    }

    

    TreeLinkNode* myrightnext(TreeLinkNode *cur){

        while(cur -> next){

            cur = cur -> next;

            if(cur -> left) return cur -> left;

            if(cur -> right) return cur -> right;

        }

        

        return NULL;

    }

    



    void connect(TreeLinkNode *root) {

        // Start typing your C/C++ solution below

        // DO NOT write int main() function

        if(!root) return;

        

        TreeLinkNode *cur = root;

        TreeLinkNode *nextLine = myNextLine(cur);

        

        while(nextLine){

            while(cur){

                if(cur -> left){

                    cur -> left -> next = myleftnext(cur);

                }

                if(cur -> right){

                    cur -> right -> next = myrightnext(cur);

                }

                

                

                cur = cur -> next;

            }

            cur = nextLine;

            nextLine = myNextLine(cur);

        }

        

    }

};
  

????

文章結(jié)束給大家分享下程序員的一些笑話語錄： 小沈陽版程序員~~~ \n程序員其實可痛苦的了......需求一做一改，一個月就過去了；嚎~ \n需求再一改一調(diào)，一季度就過去了；嚎~ \n程序員最痛苦的事兒是啥，知道不？就是，程序沒做完，需求又改了； \n程序員最最痛苦的事兒是啥，知道不？ 就是，系統(tǒng)好不容易做完了，方案全改了； \n程序員最最最痛苦的事兒是啥，知道不？ 就是，系統(tǒng)做完了，狗日的客戶跑了； \n程序員最最最最最痛苦的事兒是啥，知道不？ 就是，狗日的客戶又回來了,程序給刪沒了！

按層空間復(fù)雜度Populating Next Right Pointers in Each Node II