98. 验证二叉搜索树

题意：

解题思路：

思路：[递归+中序遍历]
1. 中序遍历后，检查是否严格上升。
2. 如果该二叉树的左子树不为空，则左子树上所有节点的值均小于它的根节点的值； 
3. 若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值；它的左右子树也为二叉搜索树。
时间复杂度 : O(n)其中n 为二叉树的节点个数。在递归调用的时候二叉树的每个节点最多被访问一次；

PHP代码实现：

class Solution {
    /**
     * @param TreeNode $root
     * @return Boolean
     */
    function isValidBST($root) {
        return $this->helper($root);
        return $this->isV($root);
        return $this->vaild($root, null, null);
    }
    function helper($root) {
        $res = [];
        $this->task($root, $res);
        for ($i = 0; $i < count($res) - 1; $i++) {
            if ($res[$i] >= $res[$i + 1]) return false;
        }
        return true;
    }
    function task($node, &$res) {
        if ($node == null) return $res;
        $this->task($node->left, $res);
        $res[] = $node->val;
        $this->task($node->right, $res);
    }    
    function vaild($root, $min, $max) {
        if (!$root) return true;
        if (!is_null($min) && $root->val <= $min) return false;
        if (!is_null($max) && $root->val >= $max) return false;
        return $this->vaild($root->left, $min, $root->val) && $this->vaild($root->right, $root->val, $max);
    }
    function isV($root) {
        if ($root == null) return true;
        //根节点为空且根节点大于左子树的最大值
        $leftVaild = $root->left == null || $root->val > $this->max($root->left)->val;
        //根节点为空且根节点小于左子树的最小值
        $rightVaild = $root->right == null || $root->val < $this->min($root->right)->val;
        return $leftVaild && $rightVaild && $this->isV($root->left) && $this->isV($root->right);
    }
    function min($root) {
        while ($root->left != null) {
            $root = $root->left;
        }
        return $root;
    }
    function max($root) {
        while ($root->right != null) {
            $root = $root->right;
        }
        return $root;
    }
}

GO代码实现：

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isValidBST(root *TreeNode) bool {
    nodes := make([]*TreeNode, 0)
    inOrder(root, &nodes)
    for i := 0;i < len(nodes) - 1;i++ {
        if nodes[i].Val >= nodes[i+1].Val {
            return false
        }
    }
    return true
}
func inOrder(root *TreeNode,nodes *[]*TreeNode) {
    if root == nil {
        return
    }
    inOrder(root.Left,nodes)
    *nodes = append(*nodes,root)
    inOrder(root.Right,nodes)
}

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isValidBST(root *TreeNode) bool {
    return helper(root, math.MinInt64, math.MaxInt64)
}
func helper(root *TreeNode, min int, max int) bool {
    if root == nil {
        return true
    }
    if root.Val <= min || root.Val >= max {
        return false
    }
    return helper(root.Left, min, root.Val) && helper(root.Right, root.Val, max)
}