给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下：
- 节点的左子树只包含 小于 当前节点的数。
- 节点的右子树只包含 大于 当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
该题有一个很大的坑，即不能只判断一个子模式下根节点大于左孩子，小于右孩子。
正确的应该是根节点大于左子树全部节点，小于右子树全部节点。
正确的做法应该使用中序遍历，全局的查看遍历顺序是否是一个递增的序列。
错误代码：
class Solution {
public:
bool isValidBST(TreeNode* root) {
if (root == nullptr) return true;
int flag = 1;
if (root->left && root->left->val >= root->val) flag = 0;
else if (root->right && root->right->val <= root->val) flag = 0;
if (flag) return isValidBST(root->left) && isValidBST(root->right);
else return false;
}
};
正确代码：
class Solution {
public:
vector path;
void traversal(TreeNode* root){
if (root == nullptr) return ;
traversal(root->left);
path.push_back(root->val);
traversal(root->right);
}
bool isValidBST(TreeNode* root) {
if (root == nullptr) return true;
traversal(root);
for(int i=0; i<path.size()-1; i++){ if (path[i] >= path[i+1]) return false;
}
return true;
}
};