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,

After calling your function, the tree should look like:

s思路： 1. o(1)的空間，注定只能用iterative的方法了。參考https://discuss.leetcode.com/topic/1106/o-1-space-o-n-complexity-iterative-solution/6 2. 由于不規(guī)則的樹結(jié)構(gòu)，所以需要用pre，cur來找到新的連接關(guān)系的兩端；還需要一個head表示每層的起點。三個指針的interplay在代碼里面寫得很清楚。每次把head賦給cur，然后根據(jù)cur->left、cur->right是否存在來更新連接:如果cur->left存在，又看pre是否已經(jīng)存在：不存在則這個節(jié)點就是head,且pre=cur->left;存在則就把這個節(jié)點作為pre的next;對cur->right也同樣判斷。 3. 多體會！