Clear O(n) space Java Solution (You should not get lost in between)


  • 0
    public class Solution {
        public TreeNode upsideDownBinaryTree(TreeNode root) {
            if(root==null)
                return null;
                
            Map<TreeNode,TreeNode> map = new HashMap<TreeNode,TreeNode>();
            Stack<TreeNode> stk = new Stack<TreeNode>();
            
            TreeNode node  = root;
            while(node!=null) {
                stk.push(node);
                if(node.right!=null)
                    map.put(node.left,node.right);
                node = node.left;
            }
            
            TreeNode newRoot = stk.peek();
            while(!stk.isEmpty()) {
                TreeNode newNode = stk.pop();
                newNode.left = map.containsKey(newNode) ? map.get(newNode) : null;
                newNode.right = stk.isEmpty() ? null : stk.peek();
            }
            
            return newRoot;
        }
    }

Log in to reply
 

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