0116. Populating Next Right Pointers in Each Node (Medium)

Question

You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. The binary tree has the following definition:

1
2
3
4
5
6

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

Follow up:

• You may only use constant extra space.
• Recursive approach is fine, you may assume implicit stack space does not count as extra space for this problem.

Example 1

1
2
3

Input: root = [1,2,3,4,5,6,7]
Output: [1,#,2,3,#,4,5,6,7,#]
Explanation: Given the above perfect binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B. The serialized output is in level order as connected by the next pointers, with '#' signifying the end of each level.

分析/解題

給定一個完美二元樹(perfect binary tree)，
也就是所有葉子都在相同level且所有父節點均有兩個子節點。
在Node的定義中增加一個next的定義，
如圖所示，每個節點的next為其右邊的節點，
如右邊已無節點，則為NULL。
(最開始的時候預設所有節點的next均為NULL)
請把整個next的定義完成。

由於這個題目已經有提到說只能用常數的額外記憶體空間了，
但同時將遞迴導致的stack(也就是call stack)當作不算，
所以使用簡單的遞迴可以簡單達到目的。

最直觀的方式，就是先檢查root是否是null，
接下來呼叫一個helper function，代入左節點和右節點來處理，
只要左節點不是NULL，則將左節點的next設為右節點；
接下來則要分別處理這三個連接：
1. 左節點的left -> 左節點的right
2. 左節點的right -> 右節點的left
3. 右節點的left -> 右節點的right

當然，也可以從root為中心出發，
這時候每次要關注的應該是root.left -> root.right，
及root.right -> root.next.left。

如果想要用迭代的方式呢？
我們留意到每次開始進行連接的都是當個階層的最左邊的節點，
從Figure B 上來看的話，即為1, 2, 4…等節點。
所以我們最開始應該要從一個階層的最左邊的節點
(這邊叫做level_first)開始進行迭代，將當前的節點稱為curr
分別將curr.left -> curr.right 及curr.right -> curr.next.left。
接著讓curr遞移到curr.next。
所以每次連接兩組next的關係，直到curr走到NULL為止。
這時候這層走完以後，進行到下一層，
level_first應該遞移到level_first.left。

依此，寫成如下的程式碼。

Java

在Java中，上述三種方法均有列出，
順序剛好跟上面提到的相反，
請務必留意在接續前必須要留意要確定節點是否為null的狀況。
如果計入call stack的話，只有迭代的方式是O(1)才對。

Python

Python的部分大同小異，不要忘記使用self來呼叫，
這邊僅列出第二種和第三種。

面試實際可能會遇到的問題

「時間/空間複雜度？」
(O(N)/O(1)，如果不考慮Call Stack的話。
如果考慮的話上面只有直接使用迴圈迭代的是O(1))

相似及延伸

Special Thanks suggestions/corrections from viewers:
(歡迎提供意見協助更正歐~)

從LeetCode學演算法，我們下次見囉，掰~

感謝大家對這系列文章的支持！這邊跟大家自我工商一下：

筆者開設的系列同名線上課程：
「從Leetcode學演算法｜基礎篇」已經上線啦！ 在這堂課中，你將學會利用十種演算法/資料結構來優化解題過程，
並實際完整練習20題 精選考古題，
進而逐漸提升到不需提示也可以突破白板題，取得工作門票！
Medium優惠(最後一波早鳥優惠了，不確定調回原價是什麼時候)： ** https://hiskio.com/courses/319?promo_code=VE9Q5VE**