LeetCode如何把二叉搜索树转换为累加树

一、什么是二叉搜索树

二叉搜索树（Binary Search Tree），又称二叉查找树或二叉排序树，它是一种特殊的二叉树，它具有以下性质：

• 1、若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
• 2、若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
• 3、任意节点的左、右子树也分别为二叉搜索树；
• 4、没有键值相等的节点。

二、什么是累加树

累加树（Binary Tree to Greater Sum Tree）是一种特殊的二叉树，它具有以下性质：

• 1、若任意节点的左子树不空，则根节点的值等于它的左子树上所有节点的值的累加和；
• 2、若任意节点的右子树不空，则根节点的值等于它的右子树上所有节点的值的累加和；
• 3、任意节点的左、右子树也分别为累加树；
• 4、没有键值相等的节点。

三、LeetCode如何把二叉搜索树转换为累加树

LeetCode提供了一种比较有效的方法来将二叉搜索树转换为累加树，这种方法的思想是：从树的最右节点开始，每个节点的值都是它的右子树上所有节点的值的累加和，然后再从树的最右节点开始，每个节点的值都是它的左子树上所有节点的值的累加和。

下面是LeetCode实现的一个示例代码：

123456789101112131415161718192021222324252627282930313233343536373839404142
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var bstToGst = function(root) {
    let sum = 0;
    // 从右节点开始，每个节点的值都是它的右子树上所有节点的值的累加和
    const traverse = (node) => {
        if (node === null) return;
        traverse(node.right);
        sum += node.val;
        node.val = sum;
        traverse(node.left);
    }
    // 从右节点开始，每个节点的值都是它的左子树上所有节点的值的累加和
    traverse(root);
    return root;
};

以上代码实现了将二叉搜索树转换为累加树的功能，从右节点开始，每个节点的值都是它的右子树上所有节点的值的累加和，然后再从右节点开始，每个节点的值都是它的左子树上所有节点的值的累加和，最终实现了将二叉搜索树转换为累加树的目的。