把二叉搜索树转换为累加树

LeetCode-538

// 逆向思维，从屁股后边开始遍历，方便累加
// 解题思路：【右根左遍历】从右开始遍历，逐步累加(包括本身val)，赋值本身
var convertBST = function(root) {
  let sum = 0
  function rec(node) {
    if(node === null) return
    // 先递归右子树
    rec(node.right)
    // 累加自身与前面遍历过的节点val
    sum += node.val
    node.val = sum // 赋值本身
    // 递归左子树
    rec(node.left)
  }
  rec(root)
  return root
}