求助：用递归实现二叉树叶子节点值求和至其父节点

需求：使用递归和仅基础控制语句（无专用函数），将二叉树所有叶子节点的值求和至其父节点，并移除叶子节点。

原代码 #

t = { val: 1, sx: { val: 8, sx: { val: 7, sx: {}, dx: {} }, dx: { val: 1, sx: {}, dx: {} } }, dx: { val: 3, sx: { val: 5, sx: {}, dx: {} }, dx: {} } };

function pota3(t) {
  if (t == null) { return }

  if (t.dx != null) {
    if (t.dx.sx == null && t.dx.dx == null) {
      t.val += t.dx.val
        delete t.dx 
    }
  }
  if (t.sx != null) {
    if (t.sx.sx == null && t.sx.dx == null) {
      t.val += t.sx.val
        delete t.sx 
    }
  }
  pota3(t.dx)
  pota3(t.sx)
}
pota3(t)

期望结果 #

t = {
  val: 1,
  sx: { val: 16,sx: {}, dx: {}},
  dx: { val: 8, sx: {}, dx:{}}
}

问题分析与修正 #

原代码核心问题是处理顺序错误：先判断当前节点的子节点是否为叶子，再递归子节点。但下层叶子需要先合并到它们的父节点，此时父节点才会变成新的叶子，才能继续合并到上层。正确顺序应该是先递归处理子节点，再处理当前节点的子节点合并逻辑。

修正后的代码：

t = { val: 1, sx: { val: 8, sx: { val: 7, sx: {}, dx: {} }, dx: { val: 1, sx: {}, dx: {} } }, dx: { val: 3, sx: { val: 5, sx: {}, dx: {} }, dx: {} } };

function pota3(t) {
  if (!t || Object.keys(t).length === 0) {
    return;
  }

  // 先递归处理左右子节点，确保下层叶子已经合并完成
  pota3(t.dx);
  pota3(t.sx);

  // 处理右子节点：如果处理后右子节点是叶子（无后代）
  if (t.dx) {
    const isDxLeaf = (!t.dx.sx || Object.keys(t.dx.sx).length === 0) && 
                     (!t.dx.dx || Object.keys(t.dx.dx).length === 0);
    if (isDxLeaf) {
      t.val += t.dx.val;
      delete t.dx;
    }
  }

  // 处理左子节点：逻辑同右子节点
  if (t.sx) {
    const isSxLeaf = (!t.sx.sx || Object.keys(t.sx.sx).length === 0) && 
                     (!t.sx.dx || Object.keys(t.sx.dx).length === 0);
    if (isSxLeaf) {
      t.val += t.sx.val;
      delete t.sx;
    }
  }
}

pota3(t);
console.log(t);

关键说明 #

1. 递归顺序调整：先递归处理dx和sx，让下层叶子节点先合并到父节点，使父节点成为新的叶子。
2. 叶子节点判断优化：原代码用null判断，但初始叶子节点是空对象{}，所以用Object.keys().length === 0判断更准确。
3. 合并逻辑后置：等子节点处理完成后，再检查子节点是否变为叶子，执行合并和删除操作。

执行修正后的代码，即可得到期望结果。

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