??博客原文 ：《LeetCode 1038.從二叉搜索樹到更大和樹 - JavaScript》

給出二叉搜索樹的根節(jié)點，該二叉樹的節(jié)點值各不相同，修改二叉樹，使每個節(jié)點 node 的新值等于 原樹中大于或等于 node.val 的值之和。

解法：改造中序遍歷

根絕二叉搜索樹的性質(zhì)，中序遍歷就是按照從小到大的順序遍歷節(jié)點。假設(shè)中序遍歷結(jié)果是：1、2、3、4。那么根據(jù)題目要求，每個節(jié)點的值更新如下：

• 4 => 4
• 3 => 4 + 3
• 2 => 4 + 3 + 2
• 1 => 4 + 3 + 2 + 1

假如先遍歷右節(jié)點，再遍歷當(dāng)前節(jié)點，最后遍歷左節(jié)點。因為之前遍歷的節(jié)點都大于當(dāng)前節(jié)點，所以當(dāng)前節(jié)點的新值就等于 之前遍歷的節(jié)點的和 + 節(jié)點自身的值。

代碼實現(xiàn)如下：

// ac地址：https://leetcode-cn.com/problems/binary-search-tree-to-greater-sum-tree/
// 原文地址：https://xxoo521.com/2020-03-06-binary-search-tree-to-greater-sum-tree/

/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var bstToGst = function(root) {
    let sum = 0; // 之前遍歷的所有節(jié)點的和
    travse(root);
    return root;

    function travse(node) {
        node.right && travse(node.right);

        node.val += sum;
        sum = node.val;

        node.left && travse(node.left);
    }
};

更多資料

若有錯誤，歡迎指正。若對您有幫助，請給個「關(guān)注+點贊」，您的支持是我更新的動力 ??

• ??Blog：劍指 Offer + Leetcode 題解
• ??Github ：https://github.com/dongyuanxin/blog
• ?? 公眾號：心譚博客