lc.98 验证二叉搜索树

描述

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

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

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

思路–中序遍历

![[Pasted image 20241128213311.png

300]]

观察可知，如上图，中序遍历的访问顺序 刚好是 二叉搜索树从小到大递增的顺序，所以我们把中序遍历到的结点值都添加到一个数组里，判断这个数组是不是严格单调递增的，就知道这棵树是不是二叉搜索树。

class Solution {
public:
    bool isValidBST(TreeNode* root){
        vector<int>vec;
        Inorder(root,vec);

        bool is=true;
        for(int i=1;i<vec.size();i++){
            if(vec[i]<=vec[i-1]){
                is=false;
            }
        }
        return is;
    }

    void Inorder(TreeNode* root,vector<int>&vec){
        if(root){

        Inorder(root->left,vec);
        vec.push_back(root->val);
        Inorder(root->right,vec);

        }
    }
};