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, 根據(jù)二叉樹中序遍歷的定義轻腺，如果是BST,則會得到一個升序的數(shù)組。利用中序遍歷可以判斷是否是BST, 只需保存前一個節(jié)點的地址酱鸭。
代碼如下：
class Solution {
public:
bool validateBST(TreeNode* root, TreeNode* &prev)
{
if(root == NULL) return true;
if(!validateBST(root->left,prev)) return false; //左子樹一直遍歷到底嗅绰，然后最后一個葉節(jié)點變成prev堂湖，root向上回朔一個節(jié)點開始比較
if(prev != NULL && root->val <= prev->val) return false; //比較prev和root的大小蜈敢，注意不可以等于
prev = root; //將root設(shè)為prev
return validateBST(root->right,prev); //比較root->right和prev
}
bool isValidBST(TreeNode* root) {
TreeNode* prev = NULL;
return validateBST(root,prev);
}
};
