# [LeetCode] 156. Binary Tree Upside Down 二叉树的上下颠倒

2021年09月15日 阅读数：1

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.java

For example:node

Given a binary tree {1,2,3,4,5},python

1ide

/ \blog

2 3递归

/ \ip

4 5it

return the root of the binary tree [4,5,2,#,#,3,1].io

4class

/ \

5 2

/ \

3 1

Java: Time: O(N), Space: O(N)

```public class Solution {
public TreeNode upsideDownBinaryTree(TreeNode root) {
if(root == null || root.left == null)return root;
TreeNode newRoot = upsideDownBinaryTree(root.left);
//root.left is newRoot everytime
root.left.left = root.right;
root.left.right = root;
root.left = null;
root.right = null;
return newRoot;
}
}
```

Java: Time: O(N), Space: O(1)

```public class Solution {
public TreeNode upsideDownBinaryTree(TreeNode root) {
TreeNode cur = root;
TreeNode pre = null;
TreeNode tmp = null;
TreeNode next = null;
while(cur != null){
next = cur.left;
//need tmp to keep the previous right child
cur.left = tmp;
tmp = cur.right;

cur.right = pre;
pre = cur;
cur = next;
}
return pre;
}
}　　```

Python:

```# Time:  O(n)
# Space: O(n)
class Solution2(object):
# @param root, a tree node
# @return root of the upside down tree
def upsideDownBinaryTree(self, root):
return self.upsideDownBinaryTreeRecu(root, None)

def upsideDownBinaryTreeRecu(self, p, parent):
if p is None:
return parent

root = self.upsideDownBinaryTreeRecu(p.left, p)
if parent:
p.left = parent.right
else:
p.left = None
p.right = parent

return root
```

Python:

```class Solution(object):
# @param root, a tree node
# @return root of the upside down tree
def upsideDownBinaryTree(self, root):
p, parent, parent_right = root, None, None

while p:
left = p.left
p.left = parent_right
parent_right = p.right
p.right = parent
parent = p
p = left

return parent　　```

C++:

```// Recursion
class Solution {
public:
TreeNode *upsideDownBinaryTree(TreeNode *root) {
if (!root || !root->left) return root;
TreeNode *l = root->left, *r = root->right;
TreeNode *res = upsideDownBinaryTree(l);
l->left = r;
l->right = root;
root->left = NULL;
root->right = NULL;
return res;
}
};　```

C++:

```// Iterative
class Solution {
public:
TreeNode *upsideDownBinaryTree(TreeNode *root) {
TreeNode *cur = root, *pre = NULL, *next = NULL, *tmp = NULL;
while (cur) {
next = cur->left;
cur->left = tmp;
tmp = cur->right;
cur->right = pre;
pre = cur;
cur = next;
}
return pre;
}
};
```