題記:寫這篇博客要主是加深自己對按層空間復雜度的認識和總結實現算法時的一些驗經和訓教,如果有錯誤請指出,萬分感謝。
????
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~
????路思是很明顯的,一層一層的找,利用前當層的next來figure out下一層的next
????第一次做的時候用了queue來實現的按層遍歷,此次才看到了 O(1)的空間復雜度。
????從新寫了一下,為了看起來路思清楚點,碼代寫的略長。
/** * 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); } } };
????
文章結束給大家分享下程序員的一些笑話語錄: 小沈陽版程序員~~~ \n程序員其實可痛苦的了......需求一做一改,一個月就過去了;嚎~ \n需求再一改一調,一季度就過去了;嚎~ \n程序員最痛苦的事兒是啥,知道不?就是,程序沒做完,需求又改了; \n程序員最最痛苦的事兒是啥,知道不? 就是,系統好不容易做完了,方案全改了; \n程序員最最最痛苦的事兒是啥,知道不? 就是,系統做完了,狗日的客戶跑了; \n程序員最最最最最痛苦的事兒是啥,知道不? 就是,狗日的客戶又回來了,程序給刪沒了!
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索:z360901061

微信掃一掃加我為好友
QQ號聯系: 360901061
您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對您有幫助就好】元
