LeetCode Validate Binary Search Tree

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.

  confused what "{1,#,2,3}" means > read more on how binary tree is serialized on OJ.

  这道题就一个难点：要会设置节点的两边限制值。

  吸收了LeetCode论坛上的建议，不使用INT_MAX 和INT_MIN，我这里使用了LLONG_MIN和LLONG_MAX。

  因为如果是用INT_MIN，那么第一个左子树的值为INT_MIN的时候就会判断为假，其实为真。

  虽然leetcode没有测试这个情况，不过健全的程序总是最好的。

  class Solution {
  public:
  	bool isValidBST(TreeNode *root) 
  	{
  		return validBST(root);
  	}
  
  	//注意：别忘记了两边的boundary：leftMax和rightMax的设置
  	/*
  	I dont think it's a good idea to use int to represent the up and low bound of a TreeNode, INT_MIN and INT_MAX maybe used by TreeNode. We can use double or just the TreeNode itself.
  	*/
  	bool validBST(TreeNode *root, long long leftMax = LLONG_MIN, long long rightMax = LLONG_MAX) 
  	{
  		if (!root) return true;
  		if (!root->left && !root->right) return true;
  		if (root->left 
  			&& (root->left->val >= root->val || root->left->val <= leftMax)) 
  			return false;
  		if (root->right 
  			&& (root->right->val <= root->val || root->right->val >= rightMax )) 
  			return false;
  
  		return validBST(root->left, leftMax, root->val) 
  			&& validBST(root->right, root->val, rightMax);
  	}
  };