通俗算法講解推薦閱讀：
【算法–鏈表】83.刪除排序鏈表中的重復元素–通俗講解
【算法–鏈表】刪除排序鏈表中的重復元素 II–通俗講解
【算法–鏈表】86.分割鏈表–通俗講解
【算法】92.翻轉鏈表Ⅱ–通俗講解
【算法–鏈表】109.有序鏈表轉換二叉搜索樹–通俗講解
【算法–鏈表】114.二叉樹展開為鏈表–通俗講解
【算法–鏈表】116.填充每個節點的下一個右側節點指針–通俗講解

---

通俗易懂講解“填充每個節點的下一個右側節點指針Ⅱ”算法題目

一、題目是啥？一句話說清

給定一個二叉樹，填充每個節點的next指針，使其指向同一層的下一個右側節點；如果找不到下一個節點，則next指針為NULL。初始時所有next指針都是NULL。

示例：

• 輸入：二叉樹（可能不完整，即不是滿二叉樹）
• 輸出：二叉樹 with next pointers filled

二、解題核心

使用層次遍歷，但不需要使用隊列，而是利用已建立的next指針來遍歷下一層。我們使用一個虛擬節點（dummy）來幫助構建下一層的鏈表，然后用當前層的next指針來訪問所有節點，同時連接下一層的節點。

這就像在每一層中，我們有一個鏈表，我們遍歷這個鏈表來處理每個節點，同時將它們的子節點連接到下一層的鏈表中，從而節省空間。

三、關鍵在哪里？（3個核心點）

想理解并解決這道題，必須抓住以下三個關鍵點：

1. 利用當前層的next指針遍歷

• 是什么：從根節點開始，當前層已經通過next指針連接起來，所以我們可以像遍歷鏈表一樣遍歷當前層。
• 為什么重要：這樣可以避免使用隊列，節省空間。我們不需要存儲所有節點，只需要幾個指針。

2. 構建下一層的鏈表

• 是什么：在處理當前層的每個節點時，我們將它的左子節點和右子節點依次添加到下一層的鏈表中。使用一個tail指針來維護下一層鏈表的尾部。
• 為什么重要：這樣我們可以按順序連接下一層的節點，為下一層的遍歷做準備，并保持節點的順序。

3. 虛擬節點（Dummy Node）的運用

• 是什么：為下一層創建一個虛擬頭節點，這樣我們可以輕松地訪問下一層的頭節點。
• 為什么重要：虛擬節點簡化了鏈表操作，避免了處理空鏈表的情況。當下一層沒有節點時，虛擬節點的next為NULL，我們可以停止循環。

四、看圖理解流程（通俗理解版本）

假設我們有這樣一個二叉樹：

        1/ \2   3/ \   \4   5   7

我們需要填充next指針。

1. 初始化：從根節點開始，當前current指向節點1。
2. 第一層處理：
   • 創建虛擬節點dummy，tail指向dummy。
   • 遍歷當前層（只有節點1）：
     • 節點1有左子節點2：將tail.next指向節點2，tail移動到節點2。
     • 節點1有右子節點3：將tail.next指向節點3，tail移動到節點3。
   • 當前層遍歷完后，current設置為dummy.next（即節點2）。
3. 第二層處理：
   • 當前current指向節點2（第二層的頭）。
   • 創建新的虛擬節點dummy，tail指向dummy。
   • 遍歷當前層（節點2和節點3通過next連接）：
     • 節點2有左子節點4：tail.next指向節點4，tail移動到節點4。
     • 節點2有右子節點5：tail.next指向節點5，tail移動到節點5。
     • 節點3有右子節點7：tail.next指向節點7，tail移動到節點7。
   • 當前層遍歷完后，current設置為dummy.next（即節點4）。
4. 第三層處理：
   • 當前current指向節點4（第三層的頭）。
   • 創建虛擬節點dummy，tail指向dummy。
   • 遍歷當前層（節點4、5、7通過next連接）：
     • 節點4沒有子節點，跳過。
     • 節點5沒有子節點，跳過。
     • 節點7沒有子節點，跳過。
   • 下一層為空，循環結束。

最終next指針：

• 節點1的next為NULL。
• 節點2的next指向節點3。
• 節點3的next為NULL。
• 節點4的next指向節點5。
• 節點5的next指向節點7。
• 節點7的next為NULL。

五、C++ 代碼實現（附詳細注釋）

#include <iostream>
using namespace std;// 二叉樹節點定義
class Node {
public: