- 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;
}
