二叉树的遍历有哪些方式？递归和迭代分别怎么写？

class TreeNode {
  constructor(val, left = null, right = null) {
    Object.assign(this, { val, left, right })
  }
}
// 按层序数组建树，null 表示空节点，和刷题平台的格式一致，如 [3, 9, 20, null, null, 15, 7]
function buildTree(values) {
  if (values.length === 0 || values[0] === null) return null
  const root = new TreeNode(values[0])
  const queue = [root]
  for (let i = 1, head = 0; i < values.length; head++) {
    const node = queue[head] // 按层序依次给队列里的节点挂左右子节点
    for (const side of ['left', 'right']) {
      const val = values[i++] ?? null // 越界也当作空节点
      if (val !== null) queue.push((node[side] = new TreeNode(val))) // 挂上子节点，再入队等着挂它的子节点
    }
  }
  return root
}

function traverse(root, order) {
  const result = []
  const dfs = (node) => {
    if (!node) return
    if (order === 'pre') result.push(node.val) // 根 左 右
    dfs(node.left)
    if (order === 'in') result.push(node.val) // 左 根 右
    dfs(node.right)
    if (order === 'post') result.push(node.val) // 左 右 根
  }
  dfs(root)
  return result
}

function inorderIterative(root) {
  const result = []
  const stack = []
  let node = root
  while (node || stack.length > 0) {
    for (; node; node = node.left) stack.push(node) // 一路向左，沿途节点都压栈
    node = stack.pop() // 左边走到头了，访问栈顶
    result.push(node.val)
    node = node.right // 转向右子树，重复上面的过程
  }
  return result
}

function levelOrder(root) {
  const levels = []
  let current = root ? [root] : []
  while (current.length > 0) {
    levels.push(current.map((node) => node.val))
    current = current.flatMap((node) => [node.left, node.right]).filter(Boolean) // 下一层的非空节点
  }
  return levels
}
console.log(levelOrder(buildTree([3, 9, 20, null, null, 15, 7]))) // [[3], [9, 20], [15, 7]]

const maxDepth = (root) => (root ? 1 + Math.max(maxDepth(root.left), maxDepth(root.right)) : 0)

function isMirror(a, b) {
  if (!a || !b) return a === b // 都为空才算对称
  return a.val === b.val && isMirror(a.left, b.right) && isMirror(a.right, b.left)
}
const isSymmetric = (root) => !root || isMirror(root.left, root.right)

function isValidBST(root) {
  let prev = -Infinity // 中序遍历中上一个访问的值
  const check = (node) => {
    if (!node) return true
    if (!check(node.left) || node.val <= prev) return false
    prev = node.val
    return check(node.right)
  }
  return check(root)
}
console.log(isValidBST(buildTree([5, 4, 6, null, null, 3, 7]))) // false：3 在 5 的右子树里