题目内容

Given a binary tree where all the right nodes are either leaf nodes with a sibling (a left node that shares the same parent node) or empty, flip it upside down and turn it into a tree where the original right nodes turned into left leaf nodes. Return the new root.

For example:
Given a binary tree {1,2,3,4,5},
    1
   / \
  2   3
 / \
4   5
return the root of the binary tree [4,5,2,null,null,3,1].
   4
  / \
 5   2
    / \
   3   1  

（因为这道题被锁住了，在写这篇文章时还有23天就要过期了，把原题也贴上来。）题目要求，树的结构是每个当右边子节点的，它肯定有个sibling，就是它的根节点肯定有个左边子节点，也就是说它是二胎。现在要把这个树从右往左看，要返回新的树。

解决思路

这道题有点儿类似反转链表，所以需要逐个修改每个节点的指向，以前的爷爷可能就是明天的孙子，曾经在工科专业成绩优秀转到CS重头再来也是这个心情。再仔细看，对于1->2->4，想逆转成4->2->1，其实就是左<-根->右变成了右<-左->根，好的办法是先找到左，然后开倒车，想办法把根和右的关系调整过来。
所以这道题用到自下而上递归的办法，先找到最左边的叶子，作为新的root，然后给新的root分配好它的left，right child。比如这个例子，先搞清楚4，5，2三个节点的关系，然后再向上找，搞1，2，3之间的关系。

两个需要注意的地方，一个是如何高效的找到4，也就是最左边的叶子。利用好递归方法的返回值，总会返回最小规模问题的返回值，也就是说，当递归终止时的返回值就是整个递归方法的返回值，之前这句话讲的很绕，我自己也在理解中。
第二，注意把原来根节点和两个子节点的指针删掉，因为最后原来的根节点一定会被变成一个叶子节点，那么叶子节点还指着根节点的话，就是个漂亮的环，会出现stackoverflow的错误。

code

public class Solution {
    public TreeNode upsideDownBinaryTree(TreeNode root) {
        //递归设置终止条件，在空节点或最左边的叶子处终止。
        if(root == null || (root.left == null && root.right == null)) return root;
        //把最左边的叶子拎出来作为新的root，留着返回
        TreeNode newRoot = upsideDownBinaryTree(root.left);
        //改各个节点之间的关系
        root.left.left = root.right;
        root.left.right = root;
        //这步非常有必要，每次改完之后把原来的节点关系都清空，否则成环
        root.left = null;
        root.right = null;
        
        return newRoot;
    }
}

复杂度分析

程序遍历了所有的节点，而且每个节点算是遍历两次，一次从上到下，一次从下到上。复杂度是O(n)。