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

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

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

解析

反中序遍历（右→根→左），累加即可。

var convertBST = function (root) {
  let sum = 0;
  function dfs(node) {
    if (!node) return;
    dfs(node.right);
    sum += node.val;
    node.val = sum;
    dfs(node.left);
  }
  dfs(root);
  return root;
};