LeetCode题解：98. 验证二叉搜索树，递归，JavaScript，详细注释

[chencl1986]

原题链接：https://leetcode-cn.com/problems/validate-binary-search-tree/

解题思路：

1. 递归遍历所有节点，每次都对比当前节点与上一个节点的大小。
2. 向左遍历则对比右侧节点的大小，及其值是否大于父节点。
3. 向右遍历则对比左侧节点的大小，及其值是否小于父节点。
4. 由于每次对比的都是相邻节点，若都满足规律，则自然保证了二叉搜索树的定义。

// 递归遍历二叉树，同时校验是否合法
function traversal(
  node, // 当前节点
  leftLimit, // 当前节点左侧节点的值
  rightLimit, // 当前节点右侧节点的值
) {
  // 递归终止条件
  // 如果当前节点为空，则默认返回true
  if (!node) {
    return true;
  }

  // 当前递归逻辑
  // 由于二叉搜索树的节点从左到右递增排列，因此如果节点的值不符合此规律则为false
  // 每次比较的都是当前节点相邻节点的值，因此比较之后就成功之后二叉树就自然符合了如下规则：
  // 左子树上所有节点的值均小于它的根节点的值；右子树上所有节点的值均大于它的根节点的值
  if (leftLimit >= node.val || node.val >= rightLimit) {
    return false;
  }

  // 继续向下递归
  // 返回子节点的判断结果，左右子节点都满足条件时，才为true
  return (
    // 向左递归，此时leftLimit始终为-Infinity，rightLimit为子节点右侧节点的值
    traversal(node.left, leftLimit, node.val) &&
    // 向右递归，此时rightLimit始终为Infinity，leftLimit为子节点左侧节点的值
    traversal(node.right, node.val, rightLimit)
  );
}
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isValidBST = function (root) {
  return traversal(root, -Infinity, Infinity);
};