二叉树基础与遍历

// 运行环境：Node.js 14+
// 保存为 dsa-l11.js，执行：node dsa-l11.js

class TreeNode {
  constructor(val, left = null, right = null) { this.val = val; this.left = left; this.right = right }
}

// 前序（根→左→右）、中序（左→根→右）、后序（左→右→根）
function preorder(root, out = []) { if (!root) return out; out.push(root.val); preorder(root.left, out); preorder(root.right, out); return out }
function inorder(root, out = [])  { if (!root) return out; inorder(root.left, out); out.push(root.val); inorder(root.right, out); return out }
function postorder(root, out = []) { if (!root) return out; postorder(root.left, out); postorder(root.right, out); out.push(root.val); return out }

// 层序遍历（BFS，用队列）
function levelOrder(root) {
  if (!root) return []
  const q = [root], res = []
  while (q.length) {
    const node = q.shift() // 小数据量无妨；生产用头指针队列
    res.push(node.val)
    if (node.left) q.push(node.left)
    if (node.right) q.push(node.right)
  }
  return res
}

// 构建示例树：    1
//               / \
//              2   3
const root = new TreeNode(1, new TreeNode(2), new TreeNode(3))
console.log('pre ', preorder(root))  // [1, 2, 3]
console.log('in  ', inorder(root))  // [2, 1, 3]
console.log('post', postorder(root)) // [2, 3, 1]
console.log('level', levelOrder(root)) // [1, 2, 3]

function preorderIter(root) {
  const res = [], st = []
  if (root) st.push(root)
  while (st.length) {
    const n = st.pop()
    res.push(n.val)
    if (n.right) st.push(n.right) // 右先入后出，保证左先处理
    if (n.left) st.push(n.left)
  }
  return res
}