36 lines
1.3 KiB
C++
36 lines
1.3 KiB
C++
#include "s0098_validate_binary_search_tree.hpp"
|
|
|
|
struct TreeNodeState_S0098 {
|
|
int maxVal;
|
|
int minVal;
|
|
bool isValidBST;
|
|
};
|
|
|
|
TreeNodeState_S0098 isValidBSTHelper(TreeNode* root) {
|
|
if (root == nullptr) return TreeNodeState_S0098{0, 0, false};
|
|
if (root->left == nullptr && root->right != nullptr) {
|
|
TreeNodeState_S0098 rightState = isValidBSTHelper(root->right);
|
|
return TreeNodeState_S0098{
|
|
rightState.maxVal, root->val,
|
|
root->val < rightState.minVal && rightState.isValidBST};
|
|
} else if (root->left != nullptr && root->right == nullptr) {
|
|
TreeNodeState_S0098 leftState = isValidBSTHelper(root->left);
|
|
return TreeNodeState_S0098{
|
|
root->val, leftState.minVal,
|
|
root->val > leftState.maxVal && leftState.isValidBST};
|
|
} else if (root->left != nullptr && root->right != nullptr) {
|
|
TreeNodeState_S0098 leftState = isValidBSTHelper(root->left);
|
|
TreeNodeState_S0098 rightState = isValidBSTHelper(root->right);
|
|
return TreeNodeState_S0098{
|
|
rightState.maxVal, leftState.minVal,
|
|
root->val > leftState.maxVal && root->val < rightState.minVal &&
|
|
leftState.isValidBST && rightState.isValidBST};
|
|
} else {
|
|
return TreeNodeState_S0098{root->val, root->val, true};
|
|
}
|
|
}
|
|
|
|
bool S0098::isValidBST(TreeNode* root) {
|
|
return isValidBSTHelper(root).isValidBST;
|
|
}
|