如何将二叉树元素查找递归函数改造为尾递归函数？

原递归函数的问题在于，递归调用后还需要对结果进行累加和布尔转换，不符合尾递归的要求（尾递归要求函数的最后一个操作就是递归调用，无后续计算）。要改成尾递归，我们可以通过维护一个待处理节点的列表，用辅助函数传递这个状态，让每次递归的最后一步都是调用自身。

尾递归实现方案 #

核心思路是用数组保存还未检查的节点，每次递归只处理当前节点，然后把未检查的子节点加入待处理列表，最后直接递归调用辅助函数：

let leaf = { val: 6 }
let tree = {
  val: 10,
  sx: {
    val: 5,
    sx: {
      val: 13
    },
    dx: leaf
  },
  dx: {
    val: 32,
    sx: null,
    dx: null
  }
}

function contains(t, x) {
  // 尾递归辅助函数，nodes是待检查的节点列表
  function tailRecursiveContains(nodes) {
    // 无待检查节点，返回false
    if (nodes.length === 0) return false;
    // 取出第一个节点
    const current = nodes[0];
    // 找到目标元素，直接返回true
    if (current.val === x) return true;
    // 收集非空的子节点，更新待处理列表
    const remainingNodes = nodes.slice(1);
    if (current.sx) remainingNodes.push(current.sx);
    if (current.dx) remainingNodes.push(current.dx);
    // 最后一步直接递归调用，无后续计算，符合尾递归要求
    return tailRecursiveContains(remainingNodes);
  }

  // 初始调用：根节点非空则加入待处理列表，否则直接返回false
  return t ? tailRecursiveContains([t]) : false;
}

console.log(contains(tree, 6)); // 输出true
console.log(contains(tree, 99)); // 输出false

为什么这是尾递归？ #

tailRecursiveContains函数的最后一个操作就是调用自身，没有任何额外的计算（比如累加、类型转换等），完全符合尾递归的定义。JavaScript引擎可以对这种形式的递归进行尾调用优化（TCO），避免栈溢出问题。

补充说明 #

• 这里用数组模拟队列，按顺序处理节点，本质是广度优先查找；如果想改成深度优先，只需要把子节点加到列表的开头（比如[current.sx, current.dx, ...remainingNodes]）即可，不影响尾递归的性质。
• 初始判断t ? ...是为了处理空树的情况，避免传入null导致报错。

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