二叉樹展開為鏈表

題目描述：給你二叉樹的根結(jié)點(diǎn) root ，請(qǐng)你將它展開為一個(gè)單鏈表：

• 展開后的單鏈表應(yīng)該同樣使用 TreeNode ，其中 right 子指針指向鏈表中下一個(gè)結(jié)點(diǎn)，而左子指針始終為 null 。

• 展開后的單鏈表應(yīng)該與二叉樹 先序遍歷 順序相同。

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

來源：力扣（LeetCode） ??

鏈接：https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list/ ??

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

解法一：遞歸

使用遞歸的方式求解，遞歸過程如下：

• 如果當(dāng)前根節(jié)點(diǎn)為null時(shí)，直接返回；

• 如果當(dāng)前根節(jié)點(diǎn)的左右子節(jié)點(diǎn)都為空時(shí)，不需要調(diào)整，直接返回；

• 如果當(dāng)前根節(jié)點(diǎn)的左子樹為空，則只需要遞歸處理當(dāng)前根節(jié)點(diǎn)的右子樹；

• 如果當(dāng)前根節(jié)點(diǎn)的右子樹為空時(shí)，則需要遞歸處理當(dāng)前根節(jié)點(diǎn)的左子樹，然后將當(dāng)前根節(jié)點(diǎn)的左子節(jié)點(diǎn)指向null，右子節(jié)點(diǎn)指向處理后的左子樹；

• 如果當(dāng)前根節(jié)點(diǎn)的左右子樹都不為空，則分別遞歸處理當(dāng)前根節(jié)點(diǎn)的左右子樹，然后將根節(jié)點(diǎn)的左子節(jié)點(diǎn)指向null，右子節(jié)點(diǎn)指向處理后的左子樹，然后將左子樹的最后一個(gè)節(jié)點(diǎn)指向處理后的右子樹。

【每日寄語】 我們的人生像云霄飛車，充滿高低與刺激，我們經(jīng)歷多，心理建設(shè)要強(qiáng)壯，眼界開，胸懷要放大。