Leetcode：98.验证二叉搜索树（C++）-创新互联

目录

问题描述：

实现代码与解析：

递归：

原理思路：

迭代（中序）：

思路原理：

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

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

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

示例 1：

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

示例 2：

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

class Solution {
public:
    void traversal(TreeNode* root,vector& vec)
    {
        if(root==NULL) return;
        traversal(root->left,vec);
        vec.push_back(root->val);//中序
        traversal(root->right,vec);

    }
    bool isValidBST(TreeNode* root) 
    {
        vectorvec;
        traversal(root,vec);
        for(int i=1;i=vec[i]) return false; 
        }
        return true;
    }
};

  根据二叉搜索树的性质，我们中序遍历转化出来的数组一定是单调递增的且没有重复元素，代码是很好写出的。

  当然也可以不用数组，直接在递归时判断出来是否有序。下面给出代码：

class Solution {
public:
    long max=LONG_MIN;
    bool isValidBST(TreeNode* root) 
    {
       if(root==NULL) return true;
       bool left=isValidBST(root->left);
       if(root->val>max) max=root->val;//更新大值
       else return false;//若不递增，不用再向右遍历了直接返回false
       bool right=isValidBST(root->right);
       return left&&right;
    }
};

  这题测试数据中有INT_MIN，所以这里我们用LONG_MIN，当然如果这里测试数据有最小的LLONG_MIN，无法找出比它还小的值，那我们就换一种方式来比较，记录前一个结点值来判断即可：

class Solution {
public:
    TreeNode* pre = NULL; // 用来记录前一个节点
    bool isValidBST(TreeNode* root) {
        if (root == NULL) return true;
        bool left = isValidBST(root->left);
        //当pre不为空
        if (pre != NULL && pre->val >= root->val) return false;
        pre = root; //记录前一个结点
        bool right = isValidBST(root->right);
        return left && right;
    }
};

  其实第一次看这个题，我想的是比较左右子树与根结点的值大小来判断返回，就像这样：

if(root->val<=root->left->val||root->val>=root->right->val) return false;

后来发现，其实这样是错误的，这样只判断左右子树的根节点，而二叉搜索树是左子树所有结点都小于根结点，右子树的所有结点都大于根节点，所以不能这样写。

class Solution {
public:
    bool isValidBST(TreeNode* root) 
    {
        stackst;
        TreeNode* pre=NULL;
        while(root!=NULL||!st.empty())
        {
            if(root!=NULL)
            {
                st.push(root);
                root=root->left;
            }
            else
            {
                root=st.top();
                st.pop();
                if(pre!=NULL&&root->val<=pre->val) return false;
                pre=root;//保存结点
                root=root->right;
            }
        }
        return true;
    }
};

  在中序遍历的代码上做一定修改即可。

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧