98. 驗證二叉搜索樹

給你一個二叉樹的根節點?root?，判斷其是否是一個有效的二叉搜索樹。

有效?二叉搜索樹定義如下：

????????節點的左子樹只包含?小于?當前節點的數。

????????節點的右子樹只包含?大于?當前節點的數。

????????所有左子樹和右子樹自身必須也是二叉搜索樹

//自己寫的
class Solution {
public:void inorderHelper(TreeNode* root, vector<int>& result) {if (root == nullptr) return;inorderHelper(root->left, result);result.push_back(root->val);inorderHelper(root->right, result);}bool isValidBST(TreeNode* root) {vector<int> res;inorderHelper(root, res);for (int i = 1; i < res.size(); i++) {if (res[i] <= res[i-1]) {return false;}}return true;}
};

最直接的想法，按中序遍歷排序，如果嚴格升序，就符合要求，能順利實現

//抄的
class Solution {
public:bool isValidBST(TreeNode* root) {return helper(root, LONG_MIN, LONG_MAX);}bool helper(TreeNode* node, long min_val, long max_val) {if (!node) return true;if (node->val <= min_val || node->val >= max_val) {return false;}return helper(node->left, min_val, node->val) && helper(node->right, node->val, max_val);}
};

遞歸做法，需要保證整個左節點樹都小于根節點，右節點大于根節點，所以需要傳遞兩個極值作為范圍。