LeetCode 1038：二叉搜索树转累加树代码中return语句的疑问解析

先看你提供的解法代码：

const bstToGst = (root) => {
    function go(root, sum) {
        if (!root) return sum;
        root.val += go(root.right, sum);
        return go(root.left, root.val);
    }
    
    go(root, 0);
    return root;
};

你已经理解if (!root) return sum（空节点直接返回传入的累加和）和root.val += go(root.right, sum)（先处理右子树，把右子树的累加和加到当前节点），这里重点解释return go(root.left, root.val)的逻辑，结合你给出的示例树一步步拆解执行过程：

示例初始树结构：

4
    /   \
  1       6
 / \     / \
0   2   5   7
     \       \
      3       8

核心逻辑前提 #

累加树要求每个节点的值 = 原节点值 + 所有比它大的节点值之和。对于BST来说，右子树所有节点都比当前节点大，左子树所有节点都比当前节点小，所以必须按「右子树 → 当前节点 → 左子树」的顺序（反中序遍历）处理，才能保证每个节点处理时，已经拿到了所有比它大的节点的累加和。

return go(root.left, root.val)的作用 #

这句话做了两件关键事：

1. 触发对左子树的处理，把当前节点更新后的值（已经包含自身+所有右子树节点的总和）传递给左子树——因为左子树节点都比当前节点小，它们的累加和需要包含当前节点及所有比当前节点大的节点，所以必须用这个更新后的值作为左子树的初始累加和。
2. 返回左子树处理完成后的最终累加和，供上层的父节点使用（父节点需要这个总和来更新自己的值）。

结合示例的完整执行流程 #

我们从根节点4开始，调用go(4, 0)：

1. 处理右子树分支（4→6→7→8）

   • 进入go(4,0)，先执行go(6, 0)
     • 进入go(6,0)，执行go(7,0)
       • 进入go(7,0)，执行go(8,0)
         • 进入go(8,0)：go(null,0)返回0，8.val += 0仍为8，然后执行return go(8.left, 8)（8.left是空节点），返回8。
       • 7.val += 8 → 7+8=15，执行return go(7.left,15)（7.left是空节点），返回15。
     • 6.val +=15 →6+15=21，执行return go(6.left,21)（即处理左子树5）
       • 进入go(5,21)：go(null,21)返回21，5.val +=21→5+21=26，执行return go(5.left,26)（空节点），返回26。
   • 此时go(6,0)返回26，4.val +=26→4+26=30。

2. 处理左子树分支（4→1→2→3）

   • 执行return go(4.left,30)（即处理左子树1）
     • 进入go(1,30)，执行go(2,30)
       • 进入go(2,30)，执行go(3,30)
         • 进入go(3,30)：go(null,30)返回30，3.val +=30→3+30=33，执行return go(3.left,33)（空节点），返回33。
       • 2.val +=33→2+33=35，执行return go(2.left,35)（空节点），返回35。
     • 1.val +=35→1+35=36，执行return go(1.left,36)（即处理左子树0）
       • 进入go(0,36)：go(null,36)返回36，0.val +=36→0+36=36，执行return go(0.left,36)（空节点），返回36。
   • go(1,30)返回36，go(4,0)执行完毕。

最终处理后的树结构：

30
    /   \
  36     21
 / \     / \
36  35  26  15
     \       \
      33      8

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