二叉树遍历与层序遍历

/*
 * 题目：二叉树遍历与层序遍历
 * 要求：输入节点含 value、left、right 的二叉树根节点 root；分别实现前序（根左右）、中序（左根右）、后序（左右根）的迭代遍历，返回一维值数组；层序从上到下逐层返回二维值数组。空树四种遍历均返回 []。
 * 示例：树 1 的左右孩子为 2、3：前序 [1,2,3]，中序 [2,1,3]，后序 [2,3,1]，层序 [[1],[2,3]]。
 */
function preorder(root) {}

function inorder(root) {}

function postorder(root) {}

function levelOrder(root) {}
const root = { value: 1, left: { value: 2, left: null, right: null }, right: { value: 3, left: null, right: null } };
console.log(preorder(root)); // 预期：[1, 2, 3]
console.log(inorder(root)); // 预期：[2, 1, 3]
console.log(postorder(root)); // 预期：[2, 3, 1]
console.log(levelOrder(root)); // 预期：[[1], [2, 3]]

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

function preorder(root) {
  if (!root) return [];
  const result = [];
  const stack = [root];
  while (stack.length) {
    const node = stack.pop();
    result.push(node.value);
    if (node.right) stack.push(node.right);
    if (node.left) stack.push(node.left);
  }
  return result;
}
function inorder(root) {
  const result = [];
  const stack = [];
  let current = root;
  while (current || stack.length) {
    while (current) {
      stack.push(current);
      current = current.left;
    }
    current = stack.pop();
    result.push(current.value);
    current = current.right;
  }
  return result;
}
function postorder(root) {
  const result = [];
  if (!root) return result;
  const stack = [[root, false]];
  while (stack.length) {
    const [node, visited] = stack.pop();
    if (visited) result.push(node.value);
    else {
      stack.push([node, true]);
      if (node.right) stack.push([node.right, false]);
      if (node.left) stack.push([node.left, false]);
    }
  }
  return result;
}
function levelOrder(root) {
  if (!root) return [];
  const result = [];
  const queue = [root];
  let head = 0;
  while (head < queue.length) {
    const size = queue.length - head;
    const level = [];
    for (let i = 0; i < size; i += 1) {
      const node = queue[head++];
      level.push(node.value);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    result.push(level);
  }
  return result;
}

// 三组以上可直接运行的验证。
const root = { value: 1, left: { value: 2, left: null, right: null }, right: { value: 3, left: null, right: null } };
console.log(preorder(root)); // 预期：[1, 2, 3]
console.log(inorder(root)); // 预期：[2, 1, 3]
console.log(postorder(root)); // 预期：[2, 3, 1]
console.log(levelOrder(root)); // 预期：[[1], [2, 3]]
console.log(levelOrder(null)); // 预期：[]