写在前面
给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下：
- 节点的左子树只包含 小于 当前节点的数。
- 节点的右子树只包含 大于 当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
提示：
- 树中节点数目范围在$[1, 10^4]$ 内
- $-2^{31} \leq Node.val \leq 2^{31} - 1$.
本质上就是中序遍历的应用, 因为二叉搜索树中序遍历的结果是一个严格的单调增序列.
第一种思路:先存数组, 然后判断
这里我一开始想的是集合去重然后判断排序数组, 但是内存飙升.
class Solution {
public:
bool isValidBST(TreeNode* root) {
if (!root) return true;
vector<int> v{};
function<void(TreeNode*)> f = [&](TreeNode* cur) {
if (!cur) return;
f(cur->left);
v.emplace_back(cur->val);
f(cur->right);
};
f(root);
auto vv(v);
set<int> s(v.begin(), v.end());
sort(v.begin(), v.end());
return s.size() == v.size() && v == vv;
}
};
那么接下来的一种改进就是直接判断数组了, 如下:
class Solution {
public:
bool isValidBST(TreeNode* root) {
if (!root) return true;
vector<int> v{};
function<void(TreeNode*)> f = [&](TreeNode* cur) {
if (!cur) return;
f(cur->left);
v.emplace_back(cur->val);
f(cur->right);
};
f(root);
for (int i{1}; i < v.size(); ++i)
if (v[i - 1] >= v[i]) return false;
return true;
}
};
但是还是不是最优解.
第二种思路: 遍历同时比较
遍历时候进行比较, 用到了中序遍历的递归写法:
class Solution {
public:
long pre = INT64_MIN;
bool isValidBST(TreeNode* root) {
if (!root) return true;
bool left = isValidBST(root->left);
if (root->val > pre)
pre = root->val;
else
return false;
bool right = isValidBST(root->right);
return left && right;
}
};
不用最小值也可以:
class Solution {
public:
TreeNode* pre{};
bool isValidBST(TreeNode* root) {
if (!root) return true;
bool left = isValidBST(root->left);
if (pre)
if (root->val > pre->val)
pre = root;
else
return false;
else
pre = root;
bool right = isValidBST(root->right);
return left && right;
}
};
判断部分看起来有点乱, 精简一下:
class Solution {
public:
TreeNode* pre{};
bool isValidBST(TreeNode* root) {
if (!root) return true;
bool left = isValidBST(root->left);
if (pre && root->val <= pre->val) return false;
pre = root;
bool right = isValidBST(root->right);
return left && right;
}
};
顺便巩固一下中序遍历迭代写法:
class Solution {
public:
bool isValidBST(TreeNode* root) {
if (!root) return true;
stack<TreeNode*> st;
TreeNode* pre{};
while (!st.empty() || root) {
if (root) {
st.push(root);
root = root->left;
} else {
root = st.top();
st.pop();
// 操作
if (pre && pre->val >= root->val) return false;
pre = root;
root = root->right;
}
}
return true;
}
};