98. Validate Binary Search Tree
98. Validate Binary Search Tree
- 推荐办法
- 只需要明白一个结论：BST树的中序遍历一定是严格递增的
- 参考：二叉排序树（BST）/二叉查找树的建立(BST是笔试面试的常客)；
- 中序走一遍，生成中序序列；
- 判断中序序列是否递增。。。
class Solution {
public:
bool isValidBST(TreeNode* root) {
if (!root) return true;
vector<int> in;
dfs(root, in);
if (in.size() == 1) return true;
else {
for (int i = 0; i < in.size() - 1; i++)
if (in[i] >= in[i+1]) return false;
return true;
}
}
void dfs(TreeNode *root, vector<int> &in) {
if (!root) return ;
dfs(root->left, in);
in.push_back(root->val);
dfs(root->right, in);
}
};
- 笨方法
- 遍历每个结点。使得该结点的键值大于所有左结点的键值，小于所有右结点的键值
- 也就是让dfs函数带着每个点的值跑遍每个子节点，看看是否符合条件。。。显然复杂度很高了
class Solution {
public:
bool isValidBST(TreeNode* root) {
if (!root) return true;
return dfs_left(root->left, root->val) && dfs_right(root->right, root->val) && isValidBST(root->left) && isValidBST(root->right);
}
bool dfs_left(TreeNode* root, int val_root) {
if (root == NULL) return true;
if (root->val >= val_root) return false;
return dfs_left(root->left, val_root) && dfs_left(root->right, val_root);
}
bool dfs_right(TreeNode* root, int val_root) {
if (root == NULL) return true;
if (root->val <= val_root) return false;
return dfs_right(root->left, val_root) && dfs_right(root->right, val_root);
}
};
