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.
Example 1:
2
/ \
1 3
Binary tree [2,1,3], return true.
Example 2:
1
/ \
2 3
Binary tree [1,2,3], return false.
解题思路:
本题要求验证二叉树是否是BST, 根据二叉树中序遍历的定义，如果是BST,则会得到一个升序的数组。利用中序遍历可以判断是否是BST, 只需保存前一个节点的地址。
代码如下：
class Solution {
public:
bool validateBST(TreeNode* root, TreeNode* &prev)
{
if(root == NULL) return true;
if(!validateBST(root->left,prev)) return false; //左子树一直遍历到底，然后最后一个叶节点变成prev，root向上回朔一个节点开始比较
if(prev != NULL && root->val <= prev->val) return false; //比较prev和root的大小，注意不可以等于
prev = root; //将root设为prev
return validateBST(root->right,prev); //比较root->right和prev
}
bool isValidBST(TreeNode* root) {
TreeNode* prev = NULL;
return validateBST(root,prev);
}
};
