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 7After calling your function, the tree should look like:
1 -> NULL / / 2 -> 3 -> NULL / / /4-> 5 -> 7 -> NULLs思路： 1. o(1)的空間，注定只能用iterative的方法了。參考https://discuss.leetcode.com/topic/1106/o-1-space-o-n-complexity-iterative-solution/6 2. 由于不規則的樹結構，所以需要用pre，cur來找到新的連接關系的兩端；還需要一個head表示每層的起點。三個指針的interplay在代碼里面寫得很清楚。每次把head賦給cur，然后根據cur->left、cur->right是否存在來更新連接:如果cur->left存在，又看pre是否已經存在：不存在則這個節點就是head,且pre=cur->left;存在則就把這個節點作為pre的next;對cur->right也同樣判斷。 3. 多體會！
//class Solution {public: void connect(TreeLinkNode *root) { // TreeLinkNode* horizon=NULL,*vertical=root; TreeLinkNode* head=root,*cur=NULL,*pre=NULL; while(head){ cur=head; pre=NULL; head=NULL; while(cur){ if(cur->left){ if(!pre){ head=cur->left; pre=head; }else{ pre->next=cur->left; pre=pre->next; } } if(cur->right){ if(!pre){ head=cur->right; pre=head; }else{ pre->next=cur->right; pre=pre->next; } } cur=cur->next; } } }};新聞熱點
疑難解答
