一、题目描述

给你二叉树的根结点 root ，请你将它展开为一个单链表：

展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
展开后的单链表应该与二叉树先序遍历顺序相同。

示例 1：

输入：root = [1,2,5,3,4,null,6]
输出：[1,null,2,null,3,null,4,null,5,null,6]

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [0]
输出：[0]

提示：

树中结点数在范围 [0, 2000] 内
-100 <= Node.val <= 100

进阶：你可以使用原地算法（O(1) 额外空间）展开这棵树吗？

二、思路讲解

题目要求按先序遍历的顺序，那么很自然地想到递归方式先序遍历每个节点，并保存到列表中，然后再串连起来。

三、Java代码实现

/**
 * 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;
 *     }
 * }
 */
class Solution {

    List<TreeNode> list = new ArrayList<>();

    public void flatten(TreeNode root) {
        dfs(root);
        TreeNode head = new TreeNode(0);
        TreeNode p = head;
        for(TreeNode node : list){
            p.right = node;
            p.left = null;
            p = p.right;
        }
        System.out.println(head.right);
    }

    void dfs(TreeNode node){
        if(node==null){
            return;
        }

        list.add(node);

        dfs(node.left);
        dfs(node.right);
    }
}

四、时空复杂度分析

时间复杂度： O(N)

空间复杂度： O(N)

五、进阶

原地改变树的结构。我们可以将第一个左节点不为空的节点（图中的节点1）的右节点（节点2）移到节点2的最后一个右子节点（节点4）之后，然后再将当前节点左子节点（节点2）移到右子节点位置上。就这样重复操作每一个右子节点不为空的节点。

/**
 * 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;
 *     }
 * }
 */
class Solution {

    public void flatten(TreeNode root) {
        
        TreeNode p = root;
        while(p!=null){
            if(p.left!=null){
                TreeNode next = p.left;
                TreeNode pre = p.left;
                while(pre.right!=null){
                    pre = pre.right;
                }
                pre.right = p.right;
                p.right = next;
                p.left = null;
            }
            p = p.right;
        }
    }
}

时间复杂度： O(N)

空间复杂度： O(1)

文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/124999.html