求修正：JavaScript实现二叉树中序遍历前驱节点的函数问题

你的原始代码存在几个核心逻辑错误：

• 未遍历树定位目标节点，仅固定检查根节点的左子树最右节点，忽略了目标可能在右子树的情况
• 当目标是根节点时错误返回null（若根节点有左子树，其前驱应为左子树最右节点）
• 未跟踪目标节点无左子树时的祖先前驱节点
• 使用未声明的current变量导致全局作用域污染

以下是修正后的函数，附带详细逻辑说明：

function inOrderPredecessor(rootNode, target) {
  let predecessor = null;
  let current = rootNode;

  while (current !== null) {
    if (current.val > target) {
      // 目标值更小，向左子树遍历
      current = current.left;
    } else if (current.val < target) {
      // 当前节点是潜在前驱（目标在其右子树，中序遍历中当前节点先于目标）
      predecessor = current;
      current = current.right;
    } else {
      // 找到目标节点
      if (current.left !== null) {
        // 前驱是左子树的最右节点
        let temp = current.left;
        while (temp.right !== null) {
          temp = temp.right;
        }
        predecessor = temp;
      }
      break; // 找到目标后退出循环
    }
  }

  // 返回前驱节点值或null（无前驱时）
  return predecessor ? predecessor.val : null;
}

关键逻辑说明 #

1. 遍历定位目标：通过比较当前节点值与目标值，向左或向右遍历树，同时跟踪潜在的前驱节点。
2. 潜在前驱跟踪：当向右子树移动时，记录当前节点为潜在前驱（因为中序遍历遵循左→根→右顺序，当前节点必然先于右子树的目标节点）。
3. 目标节点处理：
   • 若目标节点有左子树，前驱是左子树的最右节点（左子树中值最大的节点）。
   • 若目标节点无左子树，前驱为之前跟踪的潜在祖先节点。
4. 边界情况处理：若目标是中序遍历第一个节点，predecessor保持为null，直接返回null。

内容的提问来源于stack exchange，提问作者Timothy W. Times