My C++ iterative solution, O(1) Space!!!! only 32 ms!!!


  • 0
    Z

    My idea is using Harris Inorder Traversal, and without using INT_MIN or INT_MAX as sentinel, instead, I use a flag to set the first in-order value.

     class Solution {
        public:
        	bool isValidBST(TreeNode *root) {
        		if (!root)
        			return true;
        		TreeNode *now = root;
        		int lastval;
        		bool firstflag = true;
        		bool flag = true;
        		while (now)
        		{
        			if (!now->left)
        			{
        				if (firstflag)
        				{
        					firstflag = false;
        				}
        				else
        				{
        					if (now->val <= lastval)
        						flag = false;
        				}			
        				lastval = now->val;
        				now = now->right;
        			}
        			else
        			{
        				TreeNode *pre = now->left;
        				while (pre->right&&pre->right != now)
        				{
        					pre = pre->right;
        				}
        				if (pre->right == now)
        				{
        					pre->right = NULL;
        					if (now->val <= lastval)
        						flag = false;
        					lastval = now->val;
        					now = now->right;
        				}
        				else
        				{
        					pre->right = now;
        					now = now->left;
        				}
        			}
        		}
        		return flag;
        	}
        };

  • 0
    W

    As far as I know, its Morris traversal algorithm achieving O(1) space.


Log in to reply
 

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