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

心谭博客

发布于 2020-04-21 15:40:27

3420

发布于 2020-04-21 15:40:27

文章被收录于专栏：YuanXinYuanXin

给出二叉搜索树的根节点，该二叉树的节点值各不相同，修改二叉树，使每个节点 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);
    }
};

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2020-03-06，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法