Java O(N) Iterative solution and recursive solution

• Iterative Solution: Used two stacks for DFS, but only store the left node

``````public TreeNode upsideDownBinaryTree(TreeNode root) {
if(root==null || root.left==null) return root;
Stack<TreeNode> stack=new Stack<TreeNode>();
Stack<TreeNode> stackR=new Stack<TreeNode>();
TreeNode nRoot=null;
while(!stack.isEmpty()){
TreeNode node=stack.pop();
if(node.left==null){
nRoot=node;
}else if(!stackR.isEmpty() && stackR.peek()==node){
stackR.pop();
node.left.right=node;
node.left.left=node.right;
node.left=null;
node.right=null;
}else{
stack.push(node);
stackR.push(node);
stack.push(node.left);
}
}
return nRoot;
}
``````

Recursive Solution:

``````public TreeNode upsideDownBinaryTree(TreeNode root) {
if(root==null || root.left==null) return root;
TreeNode nRoot=upsideDownBinaryTree(root.left);
root.left.right=root;
root.left.left=root.right;
root.left=null;
root.right=null;
return nRoot;
}``````

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