填充每個節(jié)點的下一個右側(cè)節(jié)點指針 II

題目描述：給定一個二叉樹：

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

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

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

示例說明請見LeetCode官網(wǎng)。

來源：力扣（LeetCode）   

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

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

解法一：層序遍歷

求解過程和 LeetCode-116-填充每個節(jié)點的下一個右側(cè)節(jié)點指針 這道題完全一樣，現(xiàn)在想想，116題中提到完美二叉樹，應(yīng)該使用完美二叉樹的一些性質(zhì)有更優(yōu)的解法，而當(dāng)前的解法是通用的二叉樹的解法。

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

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

【每日寄語】 逃避壓力是沒有用的，只會讓壓力更囂張，勇敢地去面對。