My 3 Solutions for learning and discussing.


  • 0
    L

    Solution 1 : Preorder traversal.

    class Solution {
    public:
    bool isValidBST(TreeNode *root) {
        if(root == NULL) return true;
        TreeNode *pre = NULL, *post = NULL;
        if(root->left) {
            pre = root->left;
            while(pre->right) pre = pre->right;
            if(pre->val >= root->val) return false;
        }
        if(root->right) {
            post = root->right;
            while(post->left) post = post->left;
            if(post->val <= root->val) return false;
        }
        return isValidBST(root->left) && isValidBST(root->right);
    }
    };
    

    Solution 2: Inorder traversal.

    bool isBST(TreeNode *root, int& preV, bool &first) {
     if(root == NULL) return true;
     bool l = isBST(root->left, preV, first);
     if(first)  first = false;
     else if(preV >= root->val) return false;
     preV = root->val;
     bool r = isBST(root->right, preV, first);
     return l && r;
    }
    class Solution {
    public:
       bool isValidBST(TreeNode *root) {
       int preV;
       bool first = true;
       return isBST(root, preV, first);
    }
    };
    

    Solution 3: Morris Traversal.

    class Solution {
    public:
    bool isValidBST(TreeNode *root) {
    	bool result = true;
    	TreeNode *cur = root, *pre, *node1, *node2;
    	node1 = node2 = NULL;
    	while(cur) {
    		if(cur->left == NULL) {
    			if(node1 == NULL) node1 = cur;
    			else if(node2 == NULL) node2 = cur;
    			else { node1 = node2; node2 = cur; }
    			cur = cur->right;
    		} else {
    			pre = cur->left;
    			while(pre->right && pre->right != cur) pre = pre->right;
    			if(pre->right == NULL) {
    				pre->right = cur;
    				cur = cur->left;
    				continue;
    			} else {
    				pre->right = NULL;
    				if(node2 == NULL) node2 = cur;
    				else {node1 = node2; node2 = cur; }
    				cur = cur->right;
    			}
    		}
    		if(node1 && node2 && node1->val >= node2->val) 
    			result = false;
    	}
    	return result;
    }
    };
    

    Any questions ? Ask me here is OK.


  • 0
    R

    the same logic in c++ get Acceted but in java it failed in case of {1,1}. please help .

    public class Solution {

        public boolean isValidBST(TreeNode root) {
            int prev = Integer.MIN_VALUE;
            return isVal(root,prev);
        }
       public boolean isVal(TreeNode root,int prev){
            if(root == null) return true;
            boolean l = isVal(root.left,prev);
            if(prev != Integer.MIN_VALUE && prev >= root.val) return false;
            prev = root.val;
            boolean r = isVal(root.right,prev);
            return l && r;
        }
    

    }


  • 0
    S

    Pay attention to "Writing code? Select a code block and click on the button to preserve code formatting.” above text editor.


  • 0
    L

    The 2ed parameter in isVal() should be " int &". To solve it you can set "prev" as a static variable(Or try other ways can work as well).


  • 0
    J

    Solution 2 failed for {INT_MIN, INT_MIN, INT_MIN}


  • 0
    J

    failed for {MIN_VALUE, MIN_VALUE, MIN_VALUE}


  • 0
    M

    Yes, the second parameter in C++ is passed by reference, however in your Java solution is not. You can create another class Prev and use Prev.prev to implement passing by reference in Java.


  • 0
    L

    In solution 2, it assert that the minimum value in the tree is not INT_MIN, so you can do a special dispose on the solution the assertion not success .


  • 0
    J

    So how will you treat this special case? I've seen so many failed disposals on this website.


  • 0
    L

    You should have more think yourself. And I have rectified it.


  • 0
    J

    OK, I don't know why you delete your comment. I suggest using TreeNode* &prev so as to reduce the stack size.


  • 0
    Z

    Solution 3 will return the correct value about whether the BST is valid but it may modify the input tree. Consider the example {10, 5, 15, #, #, 6, 20}.


Log in to reply
 

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