给定一个二叉树的根节点 root，按照如下的方式上下翻转二叉树，并返回新的根节点。
1、原来的左子节点变成新的根节点
2、原来的根节点变成新的右子节点
3、原来的右子节点变成新的左子节点
上面的步骤都是逐层进行的，题目数据保证每个右节点都有一个同级节点（共享同一个父节点的左节点），且每个右节点不存在子节点（这个信息很关键）
整体流程
图示和题意，整个流程应逐层遍历：
1、如果当前根节点有左子节点，让左子节点的 left 指向 根节点
2、如果当前根节点有左子节点，让左子节点的right 指向根节点的右节点
3、逐层遍历，一直到 根节点 没有左子节点
思路分析
以图示为例，整体流程为 将 2 的 left 指向 1 ， right 指向 3 ，但是，直接这么做，2 的子节点信息将会丢失。
所以需要换个思路：现在将注意力集中在根节点的左子树上：
这是不是就是一个单链表，链表的头结点是 1 ，同时每个结点的左结点的 next 指针指向的是下一个结点，因此就将这个问题转换成了链表的翻转问题，剩余的问题就是根节点右子树结点怎么连接。
再观察根节点的右子树，待连接的节点有3 和 5 。需要做的就是将 2 的 right 指向 3 ，同时 4 的 right 指向 5 。所以，将新 root 的 left 指向同层节点的右子节点即可完成剩余右子节点的链接。
递归和迭代
1 public TreeNode upsideDownBinaryTree(TreeNode root) { 2 if (root == null || root.left == null) return root; 3 TreeNode prev = null; 4 TreeNode current = root; 5 TreeNode next = null; 6 TreeNode lastRight = null; 7 while (current != null) { 8 next = current.left; 9 10 current.left = lastRight; 11 lastRight = current.right; 12 13 current.right = prev; 14 prev = current; 15 current = next; 16 } 17 return prev; 18 }