PHP Code:
class Solution {
public:
bool isValidBST(TreeNode *root)
{
TreeNode *bridge, *cur, *prev;
cur = root;
while (cur)
{
if (cur->left)
{
bridge = cur->left;
while (bridge->right && bridge->right != cur)
{
bridge = bridge->right;
}
if (!bridge->right)
{
bridge->right = cur;
cur = cur->left;
}
else
{
bridge->right = NULL;
if (!cur->right)
return true;
prev = cur;
cur = cur->right;
if (prev->val >= cur->val)
return false;
}
}
else
{
if (!cur->right)
return true;
prev = cur;
cur = cur->right;
if (prev->val >= cur->val)
return false;
}
}
return true;
}
};
Leave a comment: