leetcode validate binary search tree

题目链接

• Validate Binary Search Tree

题目描述(Description)

Validate Binary Search Tree

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.

翻译

给一个二叉树，确定它是否是一个有效的二叉排序树（BST）。

一个二叉排序树定义如下：

• 一个结点（非终端结点）的值不小于其左子树的值；

• 一个结点（非终端结点）的值不大于其右子树的值；

• 所有的左子树和右子树也必须是二叉排序树。

分析

二叉排序树对我们来说其实并不陌生，因为二分法查找的逻辑就是二叉排序树。

此题的突破口是二叉树的遍历顺序：二叉排序树的中序遍历是有序的。所以只要根据中序遍历规则，依次判断是否满足二叉排序树的规则即可。

• 定义一个变量pre（本题的数据范围较大，已经超出int，经测试long long合适；

• 开始中序遍历：从左子树开始，递归左子树是否满足条件；根节点，判断pre与根节点值的大小，如果pre>=root->val，则返回false；遍历到右结点，递归右子树是否满足条件。

• 中序遍历结束，如果所有条件都满足，则返回true。

代码

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    long long pre;
    bool inorder(TreeNode *root){
        if(root==NULL)
            return true;
        if(!inorder(root->left))
            return false;
        if(pre>=root->val)
            return false;
        pre=root->val;
        if(!inorder(root->right))
            return false;
        return true;
    }
    bool isValidBST(TreeNode *root) {
        pre=numeric_limits<long long>::min();//pre初始化为最小值，`numeric_limits<long long>::min();`是C++标准程序里提供的极小值
        return inorder(root);
    }
};