验证二叉搜索树

为什么只比较父子节点不够？

• 反例: 右子树深处可能出现小于某个祖先的值, 父子比较无法发现;
• 正确判据: 每个节点的值必须落在由祖先确定的开区间 (min, max) 内;

带上下界的递归如何实现？

• 根节点的区间是 (-Infinity, Infinity);
• 进入左子树时把上界收紧为当前值; 进入右子树时把下界收紧为当前值;
• 越界立即返回 false;

const isValidBST = function (root) {
  const dfs = (node, min, max) => {
    if (node == null) return true;
    if (node.val <= min || node.val >= max) return false;
    return dfs(node.left, min, node.val) && dfs(node.right, node.val, max);
  };

  return dfs(root, -Infinity, Infinity);
};

中序遍历的做法为什么也成立？

• 依据: 二叉搜索树的中序序列严格递增;
• 实现: 中序遍历并只保留上一个节点的值, 出现不大于前值即失败;
• 复杂度: 两种方法都是时间 O(n), 空间 O(n) 递归栈;