Day 22 ：Validate BST

今天直接动手来解题吧！
我们从根（root）开始，利用Divide and Conquer来验证每一个子树（Subtree），直到我们验证到最後的叶子。

像是我们会往左验证他的左子树是否是BST，然後左子树的左子树是不是也是BST，一直到最後叶子的部分，不断重复这些行为。

其中，我们一定要知道一件事就是：每个BST都会有一个可能的 最大值 和 最小值

像是下面这张图的6，他的最小值就是５。
为什麽呢？因为他的父亲是5。
那他的最大呢？就是他的祖先10。
所以说，因为6是在10的左子树，所以他一定要比10小；
但他又在5的右子树，所以他又一定要大於5。
结论就是 5 < 6 ( node.val ) < 10

如果还不清楚，我们再来看一个。
这里的12这个左子树，它的范围最大值应该是15，最小值应该是 10。

以此类推的结论就是：
我们可以知道每个节点一定都有自己最大和最小的范围，所以我们只要验证每个节点都有在他应该有的范围内，就可以证明他是BST了！

不过我们要怎麽去寻找他的父亲跟祖父呢？
这边我采用写另外的helpValidateBst function来来完成，从root（10）开始追踪 把最大值设为无限大 最小值设为负无限大，然後开始往下检查。
每次检查都去呼叫我们的function，并且更改 max 或 min value为我们当下的node.val

左儿子一定要小於当下node.val。
举例：10的左边中，因为5一定要小於10，所以我们相当於把10当作最大值传到helper function

而右儿子一定要大於当下node.val。
举例 10的右边中，因为15一定要大於10，所以我们相当於把10当作最小值传到helper function

一直检查到最下面看到left和right都是 null 为止。
而时间复杂度的分析很明显就是 Time = O (N)，Ｎ为我们的node数，
因为我们一定要验证完每一个node。
而空间复杂度为O(d)，因为我们都是使用不断呼叫function的方式，用到了stack，而d会是我们最长的branch(depth of tree)。

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
const helpValidateBst = (root, minValue, maxValue) => {
	if( !root ) return true;
	if(root.val <= minValue || root.val >= maxValue) return false;
	return helpValidateBst(root.left, minValue, root.val) && helpValidateBst(root.right, root.val, maxValue);
}

var isValidBST = function(root) {
    return helpValidateBst(root, -Infinity, Infinity);
};

PS.在写题目前一定要阅读完整题目的定义！这一题的叙述比较严格的限定右子树一定要大於root，而左子树一定要小於root。

明日题目预告：Find the sums of the branches of a binary tree