给你二叉树的根结点 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置为null
public 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;
}