538. Convert BST to Greater Tree

题干简述：

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

BST 二叉检索树

  • 节点的左子树仅包含键 小于 节点键的节点。
  • 节点的右子树仅包含键 大于 节点键的节点。
  • 左右子树也必须是二叉搜索树。

解题思路

涉及到 BST 二叉检索树的题目，我们都要先想一想 BST 的特殊性质对于解题是否有所帮助。正如上文所说，

BST 二叉检索树

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

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

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

这个性质还有一个直观的体现，就是如果我们对二叉检索树进行中序遍历，得到的数组，必然是一个递增的数组，这也是为什么常说 BST 是有顺序的原因。譬如 leecode 提供的实例，中序遍历后的结果如下：

image

而本地，要求的结果是当前节点的值，加上所有大于等于它的节点的值的和，直观点展示，也就是：

image

此时，实际本题的解决方法就已经很明显了：通过中序遍历拿到有顺序的数组后，通过一个变量，比如说sum，存储从数组最后一项，一步步往前推进时的累加值，并将这个值与当前位置的节点值进行相加即可。这么说来可能有点绕，让我们稍微 reverse 一下数组，就会直观起来：

image

如果让所有节点从大到小排列，我们只需要通过 sum 维护当前节点前所有节点的和，并将 sum 与当前节点相加，即可得到最终所求的新的当前节点的值。那么，现在的问题就来到了如何得到这样一个从大到小排列的数组。结合我们前面提到的 BST 通过中序遍历可以得到从小到大排列的数组的结论，不难推出，我们在中序遍历时，替换一下递归左右子树的顺序，就可以得到期望的结果。

题解

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var convertBST = function(root) {
    let sum = 0;
    const dfs = (node) => {
        if (!node) return null;
        dfs(node.right);
        sum += node.val;
        node.val = sum;
        dfs(node.left);
    };
    dfs(root);
    return root;
};

Q.E.D.

Take it easy