98. 验证二叉搜索树

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

  • 节点的左子树只包含小于当前节点的数。
  • 节点的右子树只包含大于当前节点的数。
  • 所有左子树和右子树自身必须也是二叉搜索树。

Solution1：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
 * 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<TreeNode*> v;
        inorder(root,v);
        for(int i = 1; i < v.size(); i++){
            if(v[i-1]->val >= v[i]->val){
                return false;
            }
        }
        return true;
    }
    
    void inorder(TreeNode* node, vector<TreeNode*> &v){
        if(!node) return;
        inorder(node->left,v);
        v.push_back(node);
        inorder(node->right,v);
    }
};

利用二叉搜索树的中序遍历是升序的特性。

将每个元素push进一个vector中，如果vector中元素不是按升序排列，这该树不是二叉搜索树。

Solution2：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * 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) {
        return helper(root,NULL,NULL);
    }
    //返回该结点是否在指定区间内。
    bool helper(TreeNode *node, TreeNode *min, TreeNode *max){
        if(!node) return true;
        if((min && node->val <= min->val) || (max && node->val >= max->val)) return false;
        //左子节点的值不能比当前结点的值大，右节点的值不能不当前结点小。
        return helper(node->left, min, node) && helper(node->right, node, max);
    }
};

根据题目给的三条性质，所有结点及其下面的所有结点均可以构成二叉搜索树，

所以对于非叶子结点，可以以当前结点为根据，划分区间，区间内的点必须比左端点大，比右端点小。

用一个递归函数来不断更新该区间，判断该结点是否在区间内即可。