【题目描述】
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 keysless thanthe node's key.
·The right subtree of a node contains only nodes with keysgreater thanthe node's key.
·Both the left and right subtrees must also be binary search trees.
·A single node tree is a BST
给定一个二叉树，判断它是否是合法的二叉查找树(BST)
一棵BST定义为：
·节点的左子树中的值要严格小于该节点的值。
·节点的右子树中的值要严格大于该节点的值。
·左右子树也必须是二叉查找树。
·一个节点的树也是二叉查找树。
【题目链接】
www.lintcode.com/en/problem/validate-binary-search-tree/
【题目解析】
对于如何处理复杂边界条件，有两种有效的方法：
1.引入dummy node，这个对于链表头不确定时特别有效。
2.引入INT_MAX,INT_MIN等最大/最小值，对于比较类问题很有效(需要考虑到本身值就为最值，这种情况一般极少见)。
显然，对于这个问题，dummy node是不太适用，我们来探讨下取最值的可能性。从以上代码可知边界处理的关键在于需要判断root->left和root-right是否为NULL,key的比较则相对固定，分别为root->left->val和root->right->val, 由此我们自然可以联想到可以使用left_val和right_val对左右子树的key进行「包装」，在子节点与根节点的key进行比较之前对l eft_val和right_val赋值即可（这一思想在lintcode:(65) Median of two Sorted Arrays和lintcode:(93) Balanced Binary Tree中也有使用）。
【参考答案】
