一、题目描述
给你二叉树的根结点 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)
