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.
解题思路1：
1、中序遍历二叉树，并将遍历结果装进数组。
2、检查数组是否由低到高依次排列。
注意：如果两个结点值一样，也判定为false;
代码：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool isValidBST(TreeNode* root) {
vector<int> nums;
stack<TreeNode*> nodes;
TreeNode* curNode = root; while (curNode || !nodes.empty()) {
while (curNode) {
nodes.push(curNode);
curNode = curNode->left;
} curNode = nodes.top();
nodes.pop();
nums.push_back(curNode->val);
curNode = curNode->right;
} for (int i = ; i < nums.size(); ++i) {
if (nums[i] <= nums[i-])
return false;
} return true;
}
};
解题思路2：
判断一个二叉树是不是二叉搜索树，除了判断是否满足 “左侧子树所有结点 < 当前结点 < 右侧子树所有结点”的方式外；
还可以判断是否满足：
1、子树的最左结点（最小结点），大于子树的“左父亲”；
2、子树中，每个结点大于自己的左儿子；
（“左父亲”：结点是自己的右子树的左父亲）
使用中序遍历的方式，判断一个子树是否满足二叉查找树：
0、遍历之前记录子树的“左父亲”的值；
1、判断左子树是否满足二叉查找树；
2、如果此结点没有左孩子，则判断此结点值，是否大于整个子树的“左父亲”（如果树没有“左父亲”，即没有父亲或者是父亲的左子树，则跳过此步）；
3、如果此结点有左孩子，则判断此结点值，是否大于自己的左孩子；
4、将这个点作为“左父亲”，检查此结点的右子树是否是二叉查找树；
代码实现：
新建一个left指针，用于保存子树的“左父亲”或者结点左儿子;
如果当前结点是整个子树的最左结点，则left保存的是“左父亲”，结点需要>“左父亲”;
如果当前结点有左孩子，则left保存的是“左孩子”，结点需要>“左孩子”;
代码：
（注意left必须是地址形式在函数内可改，否则从左子树判定返回时，不能记录当前结点左儿子的数据）
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool isValidBST(TreeNode* root) {
TreeNode* left = NULL;
return validate(root, left);
} bool validate(TreeNode* node, TreeNode* &left) {
if (node == NULL)
return true;
if (validate(node->left, left) == false)
return false;
if (left != NULL && left->val >= node->val)
return false;
left = node;
return validate(node->right, left);
}
};