编辑代码

// 设置标准输入接口
const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

// 问题描述：从二叉树中找到最小叶子节点，并输出从根节点到该叶子节点的路径
// 输入格式：一行数字，表示二叉树的层序遍历结果，-1 表示空节点
// 输出格式：从根节点到最小叶子节点的路径上的所有节点值

void (async function () {
  // 读取输入并转换为数字数组，表示二叉树的层序遍历结果
  const tree = (await readline()).split(" ").map(Number);

  // 初始化最小叶子节点的索引和值
  let minLeafIdx = 0; // 最小叶子节点在数组中的索引
  let minLeafVal = Infinity; // 最小叶子节点的值

  // 遍历树中的所有节点，寻找最小的叶子节点
  for (let i = 0; i < tree.length; i++) {
    // 判断当前节点是否为叶子节点，需满足以下条件：
    // 1. 节点值不为 -1（不是空节点）
    // 2. 节点值小于当前找到的最小叶子值
    // 3. 左子节点不存在（超出数组范围或为-1）
    // 4. 右子节点不存在（超出数组范围或为-1）
    if (
      tree[i] !== -1 &&
      tree[i] < minLeafVal &&
      (2 * i >= tree.length || tree[2 * i] == -1) &&
      (2 * i + 1 >= tree.length || tree[2 * i + 1] == -1)
    ) {
      // 更新最小叶子节点的索引和值
      minLeafIdx = i;
      minLeafVal = tree[i];
    }
  }

  // 存储从叶子节点到根节点的路径
  const res = [minLeafVal]; // 初始化结果数组，先放入叶子节点值
  let curIdx = minLeafIdx; // 当前处理的节点索引

  // 从叶子节点向上遍历到根节点
  while (curIdx >= 0) {
    // 计算父节点索引：对于索引i，其父节点索引为 floor((i-1)/2)
    const parentIdx = Math.floor((curIdx - 1) / 2);
    // 将父节点值添加到结果数组的开头
    res.unshift(tree[parentIdx]);
    // 更新当前处理的节点为父节点
    curIdx = parentIdx;
  }

  // 输出结果：将路径数组转换为字符串并打印
  console.log(res.join(" "));
})();

// 示例说明：
// 输入：5 4 6 1 2 -1 -1
// 表示的二叉树结构：
//       5
//     /   \
//    4     6
//   / \
//  1   2
//
// 最小叶子节点是1
// 从根节点到最小叶子节点的路径是：5 4 1