algorithms/098-validate-binary-search-tree.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "genetic-target",
   "metadata": {},
   "source": [
    "### [验证二叉搜索树](https://leetcode-cn.com/problems/validate-binary-search-tree/)\n",
    "\n",
    "给定一个二叉树，判断其是否是一个有效的二叉搜索树。\n",
    "\n",
    "假设一个二叉搜索树具有如下特征：\n",
    "- 节点的左子树只包含小于当前节点的数。\n",
    "- 节点的右子树只包含大于当前节点的数。\n",
    "- 所有左子树和右子树自身必须也是二叉搜索树。\n",
    "\n",
    "#### 示例 1:\n",
    "```\n",
    "输入:\n",
    "    2\n",
    "   / \\\n",
    "  1   3\n",
    "输出: true\n",
    "```\n",
    "\n",
    "#### 示例 2:\n",
    "```\n",
    "输入:\n",
    "    5\n",
    "   / \\\n",
    "  1   4\n",
    "     / \\\n",
    "    3   6\n",
    "输出: false\n",
    "解释: 输入为: [5,1,4,null,null,3,6]。\n",
    "     根节点的值为 5 ，但是其右子节点值为 4。\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "monetary-communications",
   "metadata": {},
   "outputs": [],
   "source": [
    "class TreeNode:\n",
    "    def __init__(self, val=0, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        \n",
    "class Solution:\n",
    "    def isValidBST(self, root: TreeNode) -> bool:\n",
    "        def rangeCheck(node: TreeNode, start: int, end: int):\n",
    "            if node:\n",
    "                if start < node.val < end:\n",
    "                    return rangeCheck(node.left, start, node.val) and rangeCheck(node.right, node.val, end)\n",
    "                else:\n",
    "                    return False\n",
    "            else:\n",
    "                return True\n",
    "        \n",
    "        return rangeCheck(root, -0x800000000000, 0x7FFFFFFFFFFF)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}