验证二叉搜索树

递归

5根节点的左子树4为根节点上的所有节点都要小于5

5根节点的右子树6上的所有节点都要大于5

代码语言：javascript复制

#include<iostream>
using namespace std;
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 helper(TreeNode* root, long long lower, long long upper) 
    {
        //1.如果当前树为空，也是搜索二叉树
        //2.如果不为空，就相对判断当前二叉树是否到了叶子节点
        if (root == nullptr) {
            return true;
        }
        //如果当前节点小于下界，或者大于上界，都是不符合条件的
        if (root->val <= lower || root->val >= upper) {
            return false;
        }
        //左子树和右子树都满足条件才算是搜索二叉树
        return helper(root->left, lower, root->val) && helper(root->right, root->val, upper);
    }
    bool isValidBST(TreeNode* root) 
    {
        return helper(root, LONG_MIN, LONG_MAX);
    }
};
void test()
{
    TreeNode t1 = { 5,NULL,NULL };
    TreeNode t2 = { 4,NULL,NULL };
    TreeNode t3 = { 6,NULL,NULL };
    TreeNode t4 = { 3,NULL,NULL };
    TreeNode t5 = { 7,NULL,NULL };
    t1.left = &t2;
    t1.right = &t3;
    t3.left = &t4;
    t3.right = &t5;
    Solution s;
    bool ret = s.isValidBST(&t1);
    if (ret)
    {
        cout << "是搜索二叉树" << endl;
    }
    else
    {
        cout << "不是搜索二叉树" << endl;
    }
}
int main()
{
    test();
    system("pause");
    return 0;
}

中序遍历

JAVA代码

代码语言：javascript复制

class Solution {
    long pre = Long.MIN_VALUE;
    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }
        // 访问左子树
        if (!isValidBST(root.left)) {
            return false;
        }
        // 访问当前节点：如果当前节点小于等于中序遍历的前一个节点，说明不满足BST，返回 false；否则继续遍历。
        if (root.val <= pre) {
            return false;
        }
        pre = root.val;
        // 访问右子树
        return isValidBST(root.right);
    }
}

java 遍历 递归

0 人点赞