如何实现无需创建新节点的通用多叉树tail recursive后序遍历？

这确实是个棘手的问题——尾递归的后序遍历要比前序、层序复杂不少，核心难点在于我们需要先处理完所有子节点，才能处理父节点，而尾递归要求我们把待处理的状态手动存在栈里，不能依赖调用栈的天然递归状态。你之前的实现需要创建新节点，确实不够通用，不过我们可以通过给节点添加状态标记的方式来解决这个问题，完全不需要创建新节点，也不用依赖树的构造函数。

核心思路 #

我们不用在栈里存节点本身，而是存「状态标记 + 节点」的组合：

• [false, node]：表示这个节点的子节点还未处理，需要先处理子节点
• [true, node]：表示这个节点的所有子节点已经处理完毕，可以输出当前节点的值

这样我们就可以通过栈的顺序来控制遍历流程，完全不需要构造新节点，而且只要能获取节点的值和子节点列表，就能兼容任何结构的多叉树。

实现代码 #

// 通用尾递归后序遍历函数
// 参数：
// - getValue: 从节点中提取值的函数（比如node => node[0] 或 node => node.value）
// - getChildren: 从节点中提取子节点列表的函数（比如node => node[1] 或 node => node.children）
const tailRecursivePostOrder = (getValue, getChildren) => (root) => {
  // 尾递归辅助函数，stack是待处理的状态栈
  const rec = (stack) => {
    if (stack.length === 0) return;

    const [isProcessed, node] = stack.pop();
    if (!isProcessed) {
      // 先把当前节点标记为「待输出」（子节点处理完后再回来处理它）
      stack.push([true, node]);
      // 逆序推入子节点——因为栈是后进先出，逆序后弹出顺序就是原子节点顺序
      const children = getChildren(node);
      for (let i = children.length - 1; i >= 0; i--) {
        stack.push([false, children[i]]);
      }
    } else {
      // 子节点都处理完了，输出当前节点的值
      console.log(getValue(node));
    }
    // 尾递归调用，处理更新后的栈
    return rec(stack);
  };

  // 初始状态：根节点未处理
  return rec([[false, root]]);
};

// 测试用例：你的数组结构节点
const Node = (x, ...xs) => ([x, xs]);
const tree = Node("a", Node("b", Node("e"), Node("f", Node("k"))), Node("c"), Node("d", Node("g"), Node("h"), Node("i"), Node("j")));

// 调用遍历：适配数组结构的取值和取子节点函数
tailRecursivePostOrder(node => node[0], node => node[1])(tree);

为什么这个方案可行？ #

1. 无新节点创建：栈里只存状态标记和原节点的引用，完全不需要调用Node构造函数，也不会生成新节点。
2. 完全通用：不管你的树是数组结构、对象结构（比如{value: 'a', children: [...]}），甚至是其他自定义结构，只要传入对应的getValue和getChildren函数就能遍历。
3. 纯尾递归：rec函数的最后一步永远是调用自身，没有额外的计算逻辑，符合尾递归的定义（可以被JS引擎优化，避免栈溢出）。
4. 输出符合预期：运行这段代码会输出 E K F B C G H I J D A，和你期望的EKFBCGHIJDA完全一致。

扩展适配其他树结构 #

比如如果你的树是对象结构：

const ObjectNode = (value, ...children) => ({ value, children });
const objectTree = ObjectNode("a", ObjectNode("b", ObjectNode("e"), ObjectNode("f", ObjectNode("k"))), ObjectNode("c"), ObjectNode("d", ObjectNode("g"), ObjectNode("h"), ObjectNode("i"), ObjectNode("j")));

// 只需要修改取值函数即可
tailRecursivePostOrder(node => node.value, node => node.children)(objectTree);

内容的提问来源于stack exchange，提问作者user6445533