Two solutions: 1) 0ms O(1) space, 2) 2ms using stack

• Solution 1: using three variables to keep track of tree structure

``````public class Solution {
public TreeNode upsideDownBinaryTree(TreeNode root) {
if(root == null){
return root;
}
TreeNode left = null, right = null, node = root;
while(node != null){
TreeNode tempLeft = node.left;
TreeNode tempRight = node.right;
node.right = right;
node.left = left;
right = node;
left = tempRight;
node = tempLeft;
}
return right;
}
}
``````

Solution 2: using stack to track left most nodes of the tree

``````public class Solution {
public TreeNode upsideDownBinaryTree(TreeNode root) {
if(root == null){
return root;
}
TreeNode node = root;
while(node != null){
node = node.left;
}
TreeNode newRoot = stack.pop();
node = newRoot;
while(!stack.isEmpty()){
TreeNode top = stack.pollFirst();
node.right = top;
if(top.right != null){
node.left = top.right;
}
else {
node.left = null;
}
node = top;
top.left = null;
top.right = null;
}
return newRoot;
}
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.