题目

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

• 节点的左子树只包含小于当前节点的数。
• 节点的右子树只包含大于当前节点的数。
• 所有左子树和右子树自身必须也是二叉搜索树。

示例 1:

输入:
    2
   / \
  1   3
输出: true

示例 2:

输入:
    5
   / \
  1   4
     / \
    3   6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
     根节点的值为 5 ，但是其右子节点值为 4 。

用例补充

是时候吐槽一下官方，给的用例太少了，有时候对空值的处理错了，多提交一次我觉得很冤，有时候一些关键的用例没有，导致题意不是很直观...

• 0 只有一个 true
• 1 1 无论左面是1，还是右面是1，都不能相等
• 1 -1 true ，-1 是左面的数，比1小，可以没有右边的树
• null true

测试数据

    let node = {
      val: 2,
      left: {
        val: 1,
      },
      right: {
        val: 3,
      },
    };

踩坑解法1

这是一个平凡并且有漏洞的解法

    function isValidBST(root) {
      let flag = true;
      able(root);
      function able(root) {
        if (!root) {
          return true;
        }
        if (root.left && root.left.val >= root.val) {
          flag = false;
          return;
        }
        if (root.right && root.right.val <= root.val) {
          flag = false;
          return;
        }

        able(root.left);
        able(root.right);
      }
      return flag;
    }

流程为

• 2 => able(root.left) => return true => able(root.right);=> return true;
  无法通过下面这种情况

  
  

6 虽然小于15，但是也小于10，因该是10 - 15 之间的数，否则不符合二叉搜索数，因为6不会被找到

正确的解法1

好吧，即便这次给出全面的用例我也解不出来...

我当时想着为每一条路径建立一个数组，比较当前节点与数组中节点的大小关系，因为里面会包含左子树，也会包含右子树，当层级较深时就不知道该怎么比较了，这道题正好超出了我对递归的理解...

   function isValidBST(root) {
      function able(root, low, high) {
        if (!root) {
          return true;
        }
        if (root.val <= low || root.val >= high) {
          return false;
        }

        return (
          able(root.left, low, root.val) && able(root.right, root.val, high)
        );
      }
      return able(root, Number.MIN_SAFE_INTEGER, Number.MAX_SAFE_INTEGER);
    }

一开始 able(root, Number.MIN_SAFE_INTEGER, Number.MAX_SAFE_INTEGER);
当然也可以用-Infinity 和 Infinity，这里踩了一个坑。Number.MIN_VALUE属性是 JavaScript 里最接近 0 的正值，而不是最小的负值。

        if (!root) {
          return true;
        }

处理根节点是null，或者遍历到叶子节点

        if (root.val <= low || root.val >= high) {
          return false;
        }

注意，这里的验证思路与之前错误的解法完全不同

    let node = {
      val: 10,
      left: {
        val: 5,
      },
      right: {
        val: 15,
        left: {
          val: 6,
        },
        right: {
          val: 20,
        },
      },
    };

• 10 Number.MAX_SAFE_INTEGER>10> Number.MIN_SAFE_INTEGER 通过
• 5 10>5> Number.MIN_SAFE_INTEGER 通过
• undefined 通过
• undefined 通过
• 15 Number.MAX_SAFE_INTEGER>15> 10 通过
• 6 小于15 但是也小于10 不通过

将6改作13

• 13 15>13> 10 通过
• undefined 通过
• undefined 通过
• 20 Number.MAX_SAFE_INTEGER>20> 10 通过
• undefined 通过
• undefined 通过

利用中序遍历

不得不说，上面解法虽然秀，但多多少少有些不好理解，不是很容易想出来。