98. 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.

Example 1:

    2
   / \
  1   3

Input: [2,1,3]
Output: true

Example 2:

    5
   / \
  1   4
     / \
    3   6

Input: [5,1,4,null,null,3,6]
Output: false
Explanation: The root node's value is 5 but its right child's value is 4.

---

验证一棵二叉树是否是二叉搜索树。二叉搜索树树需要满足左孩子小于等于根节点，根节点小于等于右孩子，本题中是严格的小于关系，所以二叉搜索树的中序遍历是严格递增的。一种解法是对二叉树中序遍历，然后检查遍历结果是否是严格递增的，这种解法很简单，不赘述了。
另外一种解法是直接用递归判断，代码如下。我们在每一次递归时，都判断当前节点是否大于最小值，且小于最大值，同时把当前节点的值递归带入。代码中没有求min和max的过程，但是每次调用的时候能正确检查，里面的奥秘需要自己体会，不太好讲。
举个例子吧，下图中节点6违反了BST的规则，虽然13所在子树是BST，但是6小于根节点10，所以不是BST。本代码是怎样判断出来的呢，首先根节点传入右孩子的约束是[10,max]，15传入左孩子的约束是[10,15]，13传入左孩子的约束是[10,13]，所以6并不属于[10,13]，不属于BST。

    10
   / \
  5   15
     /  \
    13   20
   /  \
  6   14

class Solution {
public:
    bool helper(TreeNode* root, long long minVal, long long maxVal)
    {
        if (root == NULL)
            return true;
        if (root->val <= minVal || root->val >= maxVal)
            return false;
        return helper(root->left, minVal, root->val) && helper(root->right, root->val, maxVal);
    }
    bool isValidBST(TreeNode* root)
    {
        long long minVal = LLONG_MIN, maxVal = LLONG_MAX;
        return helper(root, minVal, maxVal);
    }
};

本代码提交AC，用时13MS。

二刷。原理相同，更好理解的代码：

class Solution {
public:
	bool isBST(TreeNode* root, int &max_val, int &min_val) {
		if (root == NULL) {
			max_val = INT_MIN;
			min_val = INT_MAX;
			return true;
		}
		// 以root为根的子树的最大和最小值
		max_val = root->val;
		min_val = root->val;
		if (root->left == NULL && root->right == NULL) {
			return true;
		}
		if (root->left) {
			int left_max = INT_MIN, left_min = INT_MAX;
			bool left_tree = isBST(root->left, left_max, left_min);
			if (!left_tree || left_max >= root->val)return false;
			min_val = min(min_val, left_min);
		}
		
		if (root->right) {
			int right_max = INT_MIN, right_min = INT_MAX;
			bool right_tree = isBST(root->right, right_max, right_min);
			if (!right_tree || right_min <= root->val)return false;
			max_val = max(max_val, right_max);
		}
		return true;
	}

	bool isValidBST(TreeNode* root) {
		int max_val = INT_MIN, min_val = INT_MAX;
		return isBST(root, max_val, min_val);
	}
};

本代码提交AC，用时12MS。