Tree - 98. Validate Binary Search Tree

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.

思路：

验证一棵树是否是二叉查找树，很简单的题目，判断当前节点值，是否合法，再递归求解左右子树是否是bst，递归终止条件就是叶子结点。

代码：

go：

/**

 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isValidBST(root *TreeNode) bool {
    return isValid(root, math.MinInt64, math.MaxInt64)
}

func isValid(node *TreeNode, min, max int) bool {
    if node == nil {
        return true
    }
    if node.Val >= max || node.Val <= min {return false}
    return isValid(node.Left, min, node.Val) && isValid(node.Right, node.Val, max)
}