给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下：

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

思路

  1. 递归时传递 minVal, maxVal 作为合法的上下界判定
1
2
3
4
5
6
7
8
9
10
11
12
13
14
var isValidBST = function (root) {
  const checkTree = (node, minVal, maxVal) => {
    if (!node) {
      return true
    }
    return (
      minVal < node.val &&
      node.val < maxVal &&
      checkTree(node.left, minVal, node.val) &&
      checkTree(node.right, node.val, maxVal)
    )
  }
  return checkTree(root, Number.MIN_SAFE_INTEGER, Number.MAX_SAFE_INTEGER)
}

简化空间复杂度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
var isInterleave = function (s1, s2, s3) {
  if (s1.length + s2.length !== s3.length) {
    return false
  }
  const dp = new Array(s2.length + 1).fill(false)
  dp[0] = true
  for (let j = 0; j < s2.length; ++j) {
    if (s2[j] !== s3[j]) {
      break
    }
    dp[j + 1] = true
  }
  for (let i = 0; i < s1.length; ++i) {
    dp[0] = dp[0] && s1[i] === s3[i]
    for (let j = 0; j < s2.length; ++j) {
      dp[j + 1] = (dp[j] && s2[j] === s3[i + j + 1]) || (dp[j + 1] && s1[i] === s3[i + j + 1])
    }
  }
  return dp[s2.length]
}