上下翻转二叉树

给定一个二叉树的根节点 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 }