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 tree struct 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 tree struct 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; }
