Share My Java O(n) Space Solution


  • 0
    H

    Just go down to the leftmost and return. Only one prev pointer is needed, plus a new root node pointer nroot.

        private TreeNode prev=null;
        private TreeNode nroot=null;
        public TreeNode upsideDownBinaryTree(TreeNode root) {
            if(root == null){   return null;}
            L_Visit(root);
            root.left=null;	root.right=null;
            return nroot;
        }
        
        private void L_Visit(TreeNode root){
            if(root == null){   
                return;
            }
            L_Visit(root.left);
            if(prev == null){
                prev = root;
                nroot = root;
            }else{
                if(root.right !=null){
                    prev.left=root.right;
                }else{
                    prev.left=null;
                }
                prev.right=root;
                prev=root;
            }
        }
    

Log in to reply
 

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