首页 > 代码库 > Validate Binary Search Tree

Validate Binary Search Tree

2024-08-02 12:38:09   219人阅读

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

  • The left subtree of a node contains only nodes with keys less than the node‘s key.
  • The right subtree of a node contains only nodes with keys greater than the node‘s key.
  • Both the left and right subtrees must also be binary search trees.

 判断是否是二叉搜索树有陷阱：http://blog.csdn.net/sgbfblog/article/details/7771096

C++实现代码如下，使用的是中序遍历是否为递增的序列来判断：

#include<iostream>#include<new>#include<vector>#include<climits>using namespace std;//Definition for binary treestruct TreeNode{    int val;    TreeNode *left;    TreeNode *right;    TreeNode(int x) : val(x), left(NULL), right(NULL) {}};class Solution{public:    bool isValidBST(TreeNode *root)    {        if(root==NULL)            return true;        vector<int> rvec;        preorder(root,rvec);        size_t i;        int max;        if(rvec.size())            max=rvec[0];        for(i=1;i<rvec.size();i++)        {            if(rvec[i]>max)            {                max=rvec[i];            }            else                return false;        }        return true;    }    void preorder(TreeNode *root,vector<int> &rvec)    {        if(root)        {            preorder(root->left,rvec);            rvec.push_back(root->val);            preorder(root->right,rvec);        }    }    void createTree(TreeNode *&root)    {        int i;        cin>>i;        if(i!=0)        {            root=new TreeNode(i);            if(root==NULL)                return;            createTree(root->left);            createTree(root->right);        }    }};int main(){    Solution s;    TreeNode *root;    s.createTree(root);    cout<<s.isValidBST(root)<<endl;}

错误的方法：

#include<iostream>#include<new>#include<vector>using namespace std;//Definition for binary treestruct TreeNode{    int val;    TreeNode *left;    TreeNode *right;    TreeNode(int x) : val(x), left(NULL), right(NULL) {}};class Solution{public:    bool isValidBST(TreeNode *root)    {        if(root==NULL)            return true;        if(root->left&&root->right)            return (root->left->val<root->val)&&(root->val<root->right->val)&&isValidBST(root->left)&&isValidBST(root->right);        else if(root->left)            return (root->left->val<root->val)&&isValidBST(root->left);        else if(root->right)            return (root->val<root->right->val)&&isValidBST(root->right);    }    void createTree(TreeNode *&root)    {        int i;        cin>>i;        if(i!=0)        {            root=new TreeNode(i);            if(root==NULL)                return;            createTree(root->left);            createTree(root->right);        }    }};int main(){    Solution s;    TreeNode *root;    s.createTree(root);    cout<<s.isValidBST(root)<<endl;}

 

Validate Binary Search Tree


联系
我们