二叉树 · DFS

var inorderTraversal = function(root) {
  let ans = []
  const helper = (root) => {
    if (!root) return
    helper(root.left)
    ans.push(root.val)
    helper(root.right)
  }
  helper(root)
  return ans
}

题干：判断二叉树是否是合法的 BST（左子树所有值 < 根 < 右子树所有值）。

• 每个节点必须满足 low < node.val < high
• 往左走 high 缩小为当前值，往右走 low 放大为当前值

var isValidBST = function (root) {
  const dfs = (node, low, high) => {
    if (!node) return true
    const v = node.val
    if (v <= low || v >= high) return false
    return dfs(node.left, low, v) && dfs(node.right, v, high)
  }
  return dfs(root, -Infinity, Infinity)
}

var isValidBST = function (root) {
  let ansArr = []
  let flag = true
  const helper = (node) => {
    if (!node) return
    helper(node.left)
    if (!ansArr.length) {
      ansArr.push(node.val)
    } else if (ansArr[ansArr.length - 1] < node.val) {
      ansArr.push(node.val)
    } else {
      flag = false; return
    }
    helper(node.right)
  }
  helper(root)
  return flag
}

var isSymmetric = function (root) {
  if (!root) return true
  const judgeSym = (root1, root2) => {
    if (!root1 && !root2) return true
    if (!root1 || !root2) return false
    return root1.val === root2.val
      && judgeSym(root1.left, root2.right)
      && judgeSym(root1.right, root2.left)
  }
  return judgeSym(root.left, root.right)
}

题干：二维网格中 '1' 是陆地 '0' 是水，计算岛屿数量。

• 遍历到 '1' 就 count++，然后 DFS 把连通的 '1' 全置为 '0'
• 不需要额外数组记录访问路径

var numIslands = function (grid) {
  let m = grid.length, n = grid[0].length
  let count = 0

  const dfsRender = (i, j) => {
    if (i < 0 || i >= m || j < 0 || j >= n) return
    if (parseInt(grid[i][j]) === 0) return
    grid[i][j] = '0' // 遍历后置为 0
    dfsRender(i + 1, j)
    dfsRender(i - 1, j)
    dfsRender(i, j + 1)
    dfsRender(i, j - 1)
  }

  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (parseInt(grid[i][j]) === 1) {
        count++
        dfsRender(i, j)
      }
    }
  }
  return count
}

题干：字符串 s 能否被拆分为字典中的单词组合。经典 DP，很多题有它的影子。

• dp[i] = 长度为 i 的子串能否拆分
• 双重循环：j 从 0 到 i，如果 dp[j]=true 且 s[j..i] 在字典中 → dp[i]=true

var wordBreak = function (s, wordDict) {
  const n = s.length
  const dp = new Array(n + 1).fill(false)
  const set = new Set(wordDict)
  dp[0] = true
  // 注意 i <= n，因为 i 是分界点，需要比长度大 1
  for (let i = 1; i <= n; i++) {
    for (let j = 0; j < i; j++) {
      if (!dp[j]) continue
      let trimWord = s.slice(j, i)
      if (set.has(trimWord)) {
        dp[i] = true
        break
      }
    }
  }
  return dp[n]
}