验证二叉搜索树的两种方法：递归与中序遍历

验证二叉搜索树的两种方法：递归与中序遍历

二叉搜索树（Binary Search Tree，BST）是一种特殊的二叉树，其中每个节点的值都大于其左子树中的所有节点值，且小于其右子树中的所有节点值。验证一个二叉树是否满足BST的性质，是算法和数据结构学习中的一个重要问题。本文将介绍两种常见的验证方法：递归和中序遍历。

给你一个二叉树的根节点 root，判断其是否是一个有效的二叉搜索树。

有效二叉搜索树定义如下：

• 节点的左子树只包含小于当前节点的数。
• 节点的右子树只包含大于当前节点的数。
• 所有左子树和右子树自身必须也是二叉搜索树。

示例

示例 1：

输入：root = [2,1,3]
输出：true

示例 2：

输入：root = [5,1,4,null,null,3,6]
输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4 。

方法一：递归

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 * int val;
 * TreeNode *left;
 * TreeNode *right;
 * TreeNode() : val(0), left(nullptr), right(nullptr) {}
 * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
 // 辅助函数：递归检查每个节点是否满足二叉搜索树的性质
 // 参数：
 // root: 当前节点
 // lower: 当前节点值允许的最小值（开区间）
 // upper: 当前节点值允许的最大值（开区间）
 bool isValidBST(TreeNode* root, long long lower, long long upper) {
 // 如果当前节点为空，则认为是有效的二叉搜索树
 if (root == nullptr) return true;
 // 检查当前节点的值是否在合法范围内
 // 二叉搜索树中任意节点的值应严格大于左子树所有节点的值，并严格小于右子树所有节点的值
 if (root->val <= lower || root->val >= upper) return false;
 // 递归检查左右子树
 // 左子树的所有节点值必须小于当前节点的值
 // 右子树的所有节点值必须大于当前节点的值
 return isValidBST(root->left, lower, root->val) && 
 isValidBST(root->right, root->val, upper);
 }
 // 主函数：判断给定的二叉树是否为有效的二叉搜索树
 // 参数：
 // root: 树的根节点
 bool isValidBST(TreeNode* root) {
 // 调用辅助函数，初始时整个树的节点值范围为(long最小值, long最大值)
 return isValidBST(root, LONG_MIN, LONG_MAX);
 }
};

方法二：中序遍历

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 * int val;
 * TreeNode *left;
 * TreeNode *right;
 * TreeNode() : val(0), left(nullptr), right(nullptr) {}
 * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
 bool isValidBST(TreeNode* root) {
 //中序遍历需要的栈
 stack<TreeNode*> st;
 TreeNode* node = root;
 //记录上一次的值
 long long last = LONG_MIN;
 while(node!=nullptr||!st.empty()){
 while(node!=nullptr){//一直向左子树方向
 st.push(node);
 node = node->left;
 }
 //已经到最左边了
 TreeNode* temp = st.top();
 //确保为升序序列，否则直接返回false
 if((long long)temp->val<=last) return false;
 //更新last的值
 last = temp->val;
 //再看右子树
 node = temp->right; 
 //弹出已访问节点
 st.pop();
 }
 return true;
 }
};