JAVA AC solution, using constant space(2 extra pointers)


  • 0
    J

    I am not sure whether constant space means include or exclude the calling stack in recursive function.
    If it's excluded, then my solution only uses two pointers.

    public void recoverTree(TreeNode root) {
    	if (root == null || (root.left == null && root.right == null))
    			return;
    		TreeNode[] targets=new TreeNode[2];
    		checkElement(root,null,targets);
    		if(targets[0]!=null&&targets[1]!=null){
    			int temp=targets[0].val;
    			targets[0].val=targets[1].val;
    			targets[1].val=temp;
    		}
    }
    
    private TreeNode checkElement(TreeNode cur, TreeNode pioneer,TreeNode[] targets) {
    	/*If current node has left node, then pass the pioneer to the left.
    	 * current node have no left node, then passed-in pioneer is current node's pioneer,compare them to decide the
    	 * swapped nodes.
    	 */
    	if (cur.left != null) {
    		pioneer= checkElement(cur.left, pioneer,
    				targets);
    	}
    	if (pioneer != null) {/*pioneer equals null means current node is the first node*/
    		if (cur.val < pioneer.val) {
    			if (targets[0] == null)
    				targets[0] = pioneer;
    			targets[1] = cur;
    		}
    	}
    	if(cur.right!=null)
    		return checkElement(cur.right,cur,targets);
    	else 
    		return cur;
    }

  • 0
    J

    Could you please explain more about checkElement function? Still not understand why it works. Thank you so much.


  • 0
    J

    Think about for a while, does it mean that the pioneer is always the successor of the current?


  • 0
    J

    Looks like I understand your code correctly. I have write a iteration version. But still need a stack, the worst case will be O(n) space, best is log(n).

    public class Solution {
    public void recoverTree(TreeNode root) {
    if (root == null || (root.left == null && root.right == null))
    return;
    TreeNode[] targets = new TreeNode[2];

        Stack<TreeNode> s = new Stack<TreeNode>();
        TreeNode pioneer = null;
        
        while (root != null || !s.isEmpty()) {
            while(root != null) {
                s.push(root);
                root = root.left;
            }
            
            if (!s.isEmpty()) {
                root = s.pop();
                if(pioneer != null) {
                    if (pioneer.val > root.val) {
                        if(targets[0] == null) {
                            targets[0] = pioneer;
                        }
                        targets[1] = root;
                    }
                }
                pioneer = root;
                root = root.right;
            }
        }
        
        if (targets[0] != null && targets[1] != null) {
            int temp = targets[0].val;
            targets[0].val = targets[1].val;
            targets[1].val = temp;
        }
    }
    

    }


  • 0
    O

    Actually I don't think it uses constant space, cause there are at least O(lgn) level of recursion. Each level demands constant space, which in total demands O(lgn) space.

    The space complexity is equal to some iterative traversal.


  • 0
    Z

    if the case is {1,2,#,3#}, will it work?


Log in to reply
 

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