JAVA Recursive/Iterative Way with O(1) space and O(n) time


  • 0
    K

    // Iterative way (not constant space then)

     public void recoverTree(TreeNode root) {
            	Stack<TreeNode> stk = new Stack<TreeNode>();
            	TreeNode first = null;
            	TreeNode second = null;
            	int last = Integer.MIN_VALUE;
        //iterative way to inorder traverse a tree
            	while (root != null || !stk.empty()) {
            		while (root != null) {
            			stk.push(root);
            			root = root.left;
            		}
            		root = stk.pop();
            		if (first == null) 	{
            			last = root.val;
            			first = root;
            		}
            		else {
            			if (last < root.val) {
            				last = root.val;
            				if (second == null)
            					first = root;
            			}
            			else {
            				if (second == null) {
            					second = root;
            					last = root.val;
            				}
            				else {
            					last = root.val;
            					root.val = first.val;
            					first.val = last;
            					return;
            				}
            			}
            		}
            		root = root.right;			
            	} 
        // case : 3->2->4->5 will go through here with first = 3 second = 2
            	if (first == null || second == null)
            		return;
            	int tmp = first.val;
            	first.val = second.val;
            	second.val = tmp;
            }
    

    Recursive way with constant space:

       public void recoverTree(TreeNode root) {
        	helper(root);
            if(!done){
            	int tmp = first.val;
            	first.val = second.val;
            	second.val = tmp;
            }
        }
        private TreeNode first = null;
        private TreeNode second = null;
        private int last = Integer.MIN_VALUE;
        private boolean refer = false;
        private boolean done = false;
    	private void helper(TreeNode root) {
    		if (root == null)
    			return;
    		helper(root.left);
    		if (first == null) {
    			last = root.val;
    			first = root;
    			
    		}
    		else {
    			if (last < root.val) {
    				//System.out.println(last+"|"+root.val);
    				last  = root.val;
    				if (!refer)
    					first = root;
    				
    			}
    			else {
    				if (!refer){
    					refer = true;
    					second = root;
    					last = root.val;
    				}
    				else {
    					last = root.val;
    					root.val = first.val;
    					first.val = last;
    					done = true;
    				}
    			}
    		}
    		helper(root.right);
    	}

  • 0
    J

    you are using stack, obviously this is not constant space.


  • 0
    K

    My bad. Forgot that iterative way will always need space to store TreeNode.
    New recursive way with constant space is attached


  • 0

Log in to reply
 

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