156. Binary Tree Upside Down
     https://leetcode.com/problems/binary-tree-upside-down/description/
     
     image.png
     
     首先这道题的定义，观察后发现，根会变成左下最底下的孩子。随后孩子的父亲会变成右孩子，父亲的右孩子会变成左孩子。所以需要记录孩子的父亲，那么就需要用到栈。然后根据这个规则依次还原出树。最后不要忘记把最后一个节点的左右孩子的清空。

public TreeNode upsideDownBinaryTree(TreeNode root) {
        if(root == null) return null;
        Stack<TreeNode> st = new Stack<>();
        TreeNode cur = root;
        while(cur != null){
            st.push(cur);
            cur = cur.left;
        }
        
        TreeNode head = st.pop();
        cur = head;
        while(!st.isEmpty()){
            cur.left = st.peek().right;
            cur.right = st.pop();
            cur = cur.right;
        }
        cur.left = null;
        cur.right = null;
        return head;
    }

follow up: 你可以不可以只用常数的空间。
既然是常数空间，那这道题必然是指针模型可解。指针在树里就是交换连接关系。因为这个树的特性最多只有一个SIBLING。也就是左倾，右侧只有一个孩子。我们在变换的时候，只要把三角形右边的边放下来。为了达成这个效果，我们需要一根指针放在父亲节点。一根指针放在左孩子节点上。

public TreeNode upsideDownBinaryTree(TreeNode root) {
        if(root == null) return null;
        TreeNode tmp = null;
        TreeNode prev = null;
        TreeNode cur = root;
        while(cur!=null){
            TreeNode next = cur.left;
            
            cur.left = tmp;
            tmp = cur.right;
            cur.right = prev;
            
            prev = cur;
            cur = next;
            
        }

        return prev;
    }