# My 3 Solutions for learning and discussing.

• 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.

• 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;
}
``````

}

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

• 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).

• Solution 2 failed for `{INT_MIN, INT_MIN, INT_MIN}`

• failed for `{MIN_VALUE, MIN_VALUE, MIN_VALUE}`

• 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.

• 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 .

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

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

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

• 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}.

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