一、題目

給你二叉樹的根結點 root ，請你將它展開為一個單鏈表：

展開后的單鏈表應該同樣使用 TreeNode ，其中 right 子指針指向鏈表中下一個結點，而左子指針始終為 null 。

展開后的單鏈表應該與二叉樹 先序遍歷 順序相同。

二、示例

2.1> 示例 1：

【輸入】root = [1,2,5,3,4,null,6]
【輸出】[1,null,2,null,3,null,4,null,5,null,6]

2.2> 示例 2：

【輸入】root = []
【輸出】[]

2.3> 示例 3：

【輸入】root = [0]
【輸出】[0]

提示：

• 樹中結點數(shù)在范圍 [0, 2000] 內
• -100 <= Node.val <= 100

進階：

• 你可以使用原地算法（O(1) 額外空間）展開這棵樹嗎？

三、解題思路

根據(jù)題目描述，需要我們根據(jù)給定的二叉樹，然后對其進行先序遍歷/前序遍歷，從而拼裝出一條鏈表。那么，首先我們先要弄清楚二叉樹的遍歷方式，我們以三個節(jié)點為例：node、leftNode和rightNode。遍歷方式如下所示：

【前序遍歷】node——>leftNode——>rightNode
【中序遍歷】leftNode——>node——>rightNode
【后序遍歷】leftNode——>rightNode——>node

那么，了解了先序遍歷方式之后，就可以通過遍歷一次二查樹，將樹節(jié)點TreeNode保存到List中，然后再針對List進行遍歷操作，從而構造一條先序順序的鏈表。

但是，我們從題目描述的“進階”部分可以看到它的要求，即：你可以使用原地算法（O(1) 額外空間）展開這棵樹嗎？ 那么我們就不能使用List來進行TreeNode的存儲了。我們此時就需要每當遍歷一個樹節(jié)點就進行一次鏈表拼裝操作。那怎么操作呢?

【首先】創(chuàng)建兩個指針，分別為遍歷用的指針node，和指針node的前置指針preNode；
【其次】當preNode沒有被初始化時，則preNode就指向node；
【第三】每當指針node遍歷的下一個節(jié)點時，都是將preNode節(jié)點的right指向node節(jié)點，將preNode節(jié)點的left指向null；
【第四】preNode指針移動到node指針處，然后再重復第三步驟，直至整棵樹遍歷完畢；

上面就是本題的解題思路，為了方便理解，下面我們以root = [1,2,5,3,4,null,6]為例，看一下具體的處理過程是怎么樣的。請見下圖所示：

四、代碼實現(xiàn)

class Solution {
    TreeNode preNode;
    public void flatten(TreeNode root) {
        if (root == null) return;
        TreeNode leftNode = root.left;
        TreeNode rightNode = root.right;
        if (preNode == null) preNode = root;
        else {
            preNode.right = root;
            preNode.left = null;
            preNode = root;
        }
        flatten(leftNode);
        flatten(rightNode);
    }
}
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

今天的文章內容就這些了：

寫作不易，筆者幾個小時甚至數(shù)天完成的一篇文章，只愿換來您幾秒鐘的 點贊 & 分享 。

更多技術干貨，歡迎大家關注公眾號“爪哇繆斯” ~ \(^o)/ ~ 「干貨分享，每天更新」