LeetCode 题解：98. 验证二叉搜索树，使用栈中序遍历，JavaScript，详细注释

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isValidBST = function (root) {
  let stack = []; // 使用栈进行遍历
  let current = root; // 使用节点进行遍历
  let prev = -Infinity; // 记录前一个节点的值，初始为负无穷大
  // 中序遍历二叉树
  // 遍历的过程中，可能出现current为空，而stack中有元素，即为遍历到树的最底端。
  // 也可能出现current有值而stack为空的情况，如遍历到二叉树的根节点。
  while (current || stack.length) {
    // 不断向左下遍历节点，同时将所有节点入栈
    // 这样就保证了总是从最左端开始遍历节点
    while (current) {
      stack.push(current);
      current = current.left;
    }
    // 从栈中弹出节点，即为当前遍历的节点
    // 弹出节点的顺序为从左到右。
    current = stack.pop();
    // 将当前节点的值，与前一个节点比较
    // 如果当前值小于前一个节点，则二叉搜索树不合法，直接退出循环
    if (prev >= current.val) {
      return false;
    }
    // 将当前节点的值存储为前一个节点，供下一次遍历判断
    prev = current.val;
    // 不断向右侧遍历树，如果右侧节点为空，则会从栈中弹出当前子树的根节点
    // 这样就形成了从左到右的遍历顺序
    current = current.right;
  }
  return true;
};