Is there any O(1) space solution?


  • 0
    P

    I doubt it, because traversing the BST already requires O(n) space...


  • -7
    L

    I think my solution is O(1) space and O(n) time.
    The idea is simple: When we in-order travel the tree, we only need to compare current node's value and its previous node's value. If the previous node's value is larger than current node's value, and it's first such condition, the previous node is one of swapped nodes, and if we can't find the second such condition, the node following that node is another swapped node. Otherwise the current node at second such condition is the another swapped node. I used three class variables to record these three nodes. Code is below:

    public class Solution
    {
        private TreeNode first;
        private TreeNode second;
        
        private TreeNode previous;
        
        void inorderTravel(final TreeNode root)
        {
            if (root != null)
            {
                inorderTravel(root.left);
                
                if (previous.val > root.val)
                {
                    if (null == first)
                    {
                        first = previous;
                    }
                    
                    second = root;
                }
                
                previous = root;
                
                inorderTravel(root.right);
            }
        }
        
        void recoverTree(TreeNode root)
        {
            first = null;
            second = null;
            
            final TreeNode min = new TreeNode(Integer.MIN_VALUE);
            previous = min;
            inorderTravel(root);
            
            if (first != null)
            {
                final int temp = first.val;
                first.val = second.val;
                second.val = temp;
            }
        }
    }

  • 0
    P

    I think your solution is still O(n) space, you used stack afterall when you dive into recursion.


  • 0
    L

    If you consider the stack, yes. it's O(n).


  • 0
    G

    If you consider the stack, its O(log n)

    Assuming of course a balanced binary tree. If the tree isn't balanced, then there is a worst case scenario of O(n)


Log in to reply
 

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