填充每個(gè)節(jié)點(diǎn)的下一個(gè)右側(cè)節(jié)點(diǎn)指針

題目描述：給定一個(gè) 完美二叉樹 ，其所有葉子節(jié)點(diǎn)都在同一層，每個(gè)父節(jié)點(diǎn)都有兩個(gè)子節(jié)點(diǎn)。二叉樹定義如下：

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

填充它的每個(gè) next 指針，讓這個(gè)指針指向其下一個(gè)右側(cè)節(jié)點(diǎn)。如果找不到下一個(gè)右側(cè)節(jié)點(diǎn)，則將 next 指針設(shè)置為 NULL。

初始狀態(tài)下，所有 next 指針都被設(shè)置為 NULL。

示例說(shuō)明請(qǐng)見LeetCode官網(wǎng)。

來(lái)源：力扣（LeetCode） ??

鏈接：https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node/ ??

著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

解法一：層序遍歷

• 首先，如果root為空或者左右子節(jié)點(diǎn)都為空，則不需要處理next指針，直接返回root。

• 否則，當(dāng)二叉樹不只有一個(gè)節(jié)點(diǎn)時(shí)，利用隊(duì)列對(duì)二叉樹進(jìn)行層序遍歷記錄二叉樹每一層的節(jié)點(diǎn)，然后按順序處理當(dāng)前層每一個(gè)節(jié)點(diǎn)的next指針。由于處理過(guò)程中所有的節(jié)點(diǎn)順序并沒有進(jìn)行改變，所以最后返回root。

【每日寄語(yǔ)】 好好學(xué)習(xí)，天天向上。