LeetCode 1038.从二叉搜索树到更大和树

📖博客原文 ：《LeetCode 1038.从二叉搜索树到更大和树 - JavaScript》

给出二叉搜索树的根节点，该二叉树的节点值各不相同，修改二叉树，使每个节点 node 的新值等于 原树中大于或等于 node.val 的值之和。

解法：改造中序遍历

根绝二叉搜索树的性质，中序遍历就是按照从小到大的顺序遍历节点。假设中序遍历结果是：1、2、3、4。那么根据题目要求，每个节点的值更新如下：

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

假如先遍历右节点，再遍历当前节点，最后遍历左节点。因为之前遍历的节点都大于当前节点，所以当前节点的新值就等于 之前遍历的节点的和 + 节点自身的值。

代码实现如下：

// 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; // 之前遍历的所有节点的和
    travse(root);
    return root;

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

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

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

更多资料

若有错误，欢迎指正。若对您有帮助，请给个「关注+点赞」，您的支持是我更新的动力 👇

• 📖Blog：剑指 Offer + Leetcode 题解
• 🐱Github ：https://github.com/dongyuanxin/blog
• 🌟 公众号：心谭博客