Java O(N) Iterative solution and recursive solution


  • 1
    W

    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>();
            stack.add(root);
            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;
        }

Log in to reply
 

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