• Time:O(n)
• Space:O(h)

## C++

``````class Solution {
public:
TreeNode* upsideDownBinaryTree(TreeNode* root) {
if (!root || !root->left)
return root;

TreeNode* newRoot = upsideDownBinaryTree(root->left);
root->left->left = root->right;  // 2's left = 3 (root's right)
root->left->right = root;        // 2's right = 1 (root)
root->left = nullptr;
root->right = nullptr;
return newRoot;
}
};
``````

## JAVA

``````class Solution {
public TreeNode upsideDownBinaryTree(TreeNode root) {
if (root == null || root.left == null)
return root;

TreeNode newRoot = upsideDownBinaryTree(root.left);
root.left.left = root.right; // 2's left = 3 (root's right)
root.left.right = root;      // 2's right = 1 (root)
root.left = null;
root.right = null;
return newRoot;
}
}
``````

## Python

``````class Solution:
def upsideDownBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if not root or not root.left:
return root

newRoot = self.upsideDownBinaryTree(root.left)
root.left.left = root.right  # 2's left = 3 (root's right)
root.left.right = root  # 2's right = 1 (root)
root.left = None
root.right = None
return newRoot
``````

• Time:O(n)
• Space:O(1)

## C++

``````class Solution {
public:
TreeNode* upsideDownBinaryTree(TreeNode* root) {
TreeNode* prevRoot = nullptr;
TreeNode* prevRightChild = nullptr;

while (root) {
TreeNode* nextRoot = root->left;  // cache next root
root->left = prevRightChild;
prevRightChild = root->right;
root->right = prevRoot;
prevRoot = root;  // record previous root
root = nextRoot;  // update root
}

return prevRoot;
}
};
``````

## JAVA

``````class Solution {
public TreeNode upsideDownBinaryTree(TreeNode root) {
TreeNode prevRoot = null;
TreeNode prevRightChild = null;

while (root != null) {
TreeNode nextRoot = root.left; // cache next root
root.left = prevRightChild;
prevRightChild = root.right;
root.right = prevRoot;
prevRoot = root; // record previous root
root = nextRoot; // update root
}

return prevRoot;
}
}
``````

## Python

``````class Solution:
def upsideDownBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
prevRoot = None
prevRightChild = None

while root:
nextRoot = root.left  # cache next root
root.left = prevRightChild
prevRightChild = root.right
root.right = prevRoot
prevRoot = root  # record previous root
root = nextRoot  # update root

return prevRoot
``````