[1038] 把二叉搜索树转换为累加树

给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。

提醒一下，二叉搜索树满足下列约束条件：

节点的左子树仅包含键 小于 节点键的节点。

节点的右子树仅包含键 大于 节点键的节点。

左右子树也必须是二叉搜索树。

示例 1：

输入：[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]

输出：[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]

示例 2：

输入：root = [0,null,1]

输出：[1,null,1]

示例 3：

输入：root = [1,0,2]

输出：[3,3,2]

示例 4：

输入：root = [3,2,4,1]

输出：[7,9,4,10]

提示：

树中的节点数介于 1 和 100 之间。

每个节点的值介于 0 和 100 之间。

树中的所有值 互不相同 。

给定的树为二叉搜索树。

这道题与 538 题一模一样，因此参照该题的解法解答就好。

这道题提出了一个叫做累加树的概念。

我们可以发现，累加树的形成实际上就是将 BST 经过中序遍历后得到的从小到大排列的数据，从后向前开始累加，并在每个节点保留当前累加的值。

这就要求我们反向遍历树节点，并利用变量存储当前累加的值。

那么反向遍历树该怎么做呢？其实很简单，仍然属于中序遍历的一种，只需要将中序遍历先左后右的规矩改变成先右后左即可。接下来问题便迎刃而解了。

var bstToGst = function(root) {
  let sum = 0;
  function traverse(root) {
    if (!root) return;

    traverse(root.right);

    sum += root.val;
    root.val = sum;

    traverse(root.left);
  }

  traverse(root);
  return root;
};