- Binary Tree Upside Down
https://leetcode.com/problems/binary-tree-upside-down/description/
image.png
首先這道題的定義牛郑，觀察后發(fā)現(xiàn)愕提，根會變成左下最底下的孩子秋冰。隨后孩子的父親會變成右孩子钥弯，父親的右孩子會變成左孩子祭刚。所以需要記錄孩子的父親译隘，那么就需要用到棧粗恢。然后根據(jù)這個規(guī)則依次還原出樹薇正。最后不要忘記把最后一個節(jié)點的左右孩子的清空片酝。
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: 你可以不可以只用常數(shù)的空間。
既然是常數(shù)空間挖腰，那這道題必然是指針模型可解雕沿。指針在樹里就是交換連接關(guān)系。因為這個樹的特性最多只有一個SIBLING猴仑。也就是左傾审轮，右側(cè)只有一個孩子。我們在變換的時候宁脊，只要把三角形右邊的邊放下來断国。為了達成這個效果，我們需要一根指針放在父親節(jié)點榆苞。一根指針放在左孩子節(jié)點上稳衬。
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;
}
