这道题我们可以利用栈来做，利用栈先进后出的特性 每次先加入右节点再加入左节点，这样的话弹出的时候正好左节点在前面，右节点在后面满足题目要求。

然后至于是构造单链表，我们可以用一个prev节点 prev的left永远都是null 而prev的right永远都等于cur 

因为每次curr都是栈内弹出来的 按照左节点后进先出，所以prev的右节点每次其实都是原来二叉树的左节点，这样的话就能保证满足原二叉树的先序遍历。

代码如下：

public class flatten {class  Solution{public void flatten(TreeNode root) {// 利用栈来解决 每次从栈内弹出一个节点作为当前访问的节点，获得该节点的子节点，如果子节点不为空，则以此右左节点压入栈内if(root == null) return;Deque<TreeNode> stack = new LinkedList<TreeNode>();stack.push(root);TreeNode prev = null;while(!stack.isEmpty()) {TreeNode curr=stack.pop();if(prev != null) {prev.left=null;prev.right=curr;}TreeNode left=curr.left;TreeNode right=curr.right;if(right != null) {stack.push(right);}if(left != null) {stack.push(left);}prev=curr;}}}
}