验证二叉搜索树
对每个结点的左子树和右子树进行递归验证是否为二叉搜索树，如果左右子树都是二叉搜索树且与根节点比较没问题，然后返回true
class Solution {
public:
bool isValidBST(TreeNode* root) {
return dfs(root, LLONG_MIN, LLONG_MAX);
}
bool dfs(TreeNode* root, long long lower, long long upper) {
if (root == nullptr) return true;
if (root->val <= lower || root->val >= upper) return false;
bool leftValid = dfs(root->left, lower, root->val);
bool rightValid = dfs(root->right, root->val, upper);
return leftValid && rightValid;
}
};
时间复杂度： O(n) ，需遍历树中所有 n 个节点一次。 空间复杂度： O(n)
查看12道真题和解析
投递哔哩哔哩等公司6个岗位