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.
比较简单,中序遍历,并保持上一个被遍历的值与当前值比较就行了。
代码如下:
/** * 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) { // Start typing your C/C++ solution below // DO NOT write int main() function if ( !root ) return true; pre=-1000000; return check(root); } bool check(TreeNode* root) { if ( !root ) return true; if ( check(root->left) ) { if ( root->val <= pre) return false; pre=root->val; return check(root->right); } else return false; } int pre; };