给你二叉树的根结点 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) 额外空间）展开这棵树吗？
思路：下面是满足进阶要求的代码，具体就是根据左右子节点各种情况分别作出相应处理，特别注意左右子节点都不为空的时候，要将左子树调整后的最后一个节点和右子树第一个节点连接。By the way，千万不要像我一样把要求使用O(1)额外空间以为成总共使用O(1)空间，也是醉了~
TreeNode search=new TreeNode(0);public void flatten(TreeNode root) {if(root==null)return;preorderTraversal(root);}// 讨论左右孩子各种情况，不要忘记left置为nullpublic TreeNode preorderTraversal(TreeNode root) { if(root.left==null&&root.right==null) return root; // 递归返回的是开始递归的节点，不是最后一个节点，因此要设置查找指针找到最后一个节点else if(root.left!=null&&root.right==null){ root.right=root.left;root.left=null;preorderTraversal(root.right);}else if(root.right!=null&&root.left==null){preorderTraversal(root.right);}//****************** */// 左子树最后一个节点和右子树第一个节点连接else if(root.left!=null&&root.right!=null){preorderTraversal(root.right);search=preorderTraversal(root.left);while(search.right!=null)search=search.right;search.right=root.right;root.right=root.left;root.left=null;}return root;}