//    1
//   /  \
//  2    3

function preorderTraversal(root: TreeNode | null): number[] {
  if (!root) return []
  return dfs(root)
}
function dfs(node: TreeNode, result: number[] = []) {
  // 先自己，依次左子节点，右子节点
  result.push(node.val)
  if (node.left) dfs(node.left, result)
  if (node.right) dfs(node.right, result)
  return result
}

//    1
//   /  \
//  2    3

function inorderTraversal(root: TreeNode | null): number[] {
  if (!root) return []
  return dfs(root)
}
function dfs(node: TreeNode, result: number[] = []) {
  // 先左子节点，依次自己，右子节点
  if (node.left) dfs(node.left, result)
  result.push(node.val)
  if (node.right) dfs(node.right, result)
  return result
}

//    1
//   /  \
//  2    3

function postorderTraversal(root: TreeNode | null): number[] {
  if (!root) return []
  return dfs(root)
}
function dfs(node: TreeNode, result: number[] = []) {
  // 依次左，右子节点，最后自己
  if (node.left) dfs(node.left, result)
  if (node.right) dfs(node.right, result)
  result.push(node.val)
  return result
}