来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/validate-binary-search-tree 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。 有效 二叉搜索树定义如下： 节点的左子树只包含 小于 当前节点的数。 节点的右子树只包含 大于 当前节点的数。 所有左子树和右子树自身必须也是二叉搜索树。

解答

需要注意的是：

  1. 所有的左子节点都小于当前节点

  2. 所有的右子节点都大于当前节点

    1. /**
    2. * Definition for a binary tree node.
    3. * function TreeNode(val, left, right) {
    4. *     this.val = (val===undefined ? 0 : val)
    5. *     this.left = (left===undefined ? null : left)
    6. *     this.right = (right===undefined ? null : right)
    7. * }
    8. */
    9. /**
    10. * @param {TreeNode} root
    11. * @return {boolean}
    12. */
    13. var isValidBST = function(root) {
    14.  let isValid = true;
    15.  function traverse (node) {
    16.      if (!node) return;
    18.      const val = node.val;
    19.      if (!node.left && !node.right) {
    20.          return [ val ];
    21.      }
    23.      let leftNodes = traverse(node.left) || [];
    24.      let rightNodes = traverse(node.right) || [];
    26.      for (let i = 0, len = leftNodes.length; i < len; i++) {
    27.          if (leftNodes[i] >= val) {
    28.              isValid = false;
    29.          }
    30.      }
    32.      for (let i = 0, len = rightNodes.length; i < len; i++) {
    33.          if (rightNodes[i] <= val) {
    34.              isValid = false;
    35.          }
    36.      }
    38.      return [...leftNodes, val, ...rightNodes];
    39.  }
    40.  traverse(root);
    42.  return isValid;
    43. };

    优化

    把每个节点的范围区间利用闭包传进去

    1. var isValidBST = function(root) {
    2.  return helper(root, -Infinity, Infinity);
    3. }
    4. function helper (node, low, high) {
    5.  if (!node) return true;
    6.  if (node.val <= low || node.val >= high) return false;
    7.  return helper(node.left, low, node.val) && helper(node.right, node.val, high);
    8. }