【刷leetcode，拿Offer-019】1038. Binary Search Tree to Greater Sum Tree

题目链接：https://leetcode.com/problems/binary-search-tree-to-greater-sum-tree/

题面：

1038. Binary Search Tree to Greater Sum Tree

Medium

14918FavoriteShare

Given the root of a binary search tree with distinct values, modify it so that every node has a new value equal to the sum of the values of the original tree that are greater than or equal to node.val.

As a reminder, a binary search tree is a tree that satisfies these constraints:

The left subtree of a node contains only nodes with keys less than the node's key.
The right subtree of a node contains only nodes with keys greater than the node's key.
Both the left and right subtrees must also be binary search trees.

Example 1:

Input: [4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
Output: [30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]

Note:

The number of nodes in the tree is between 1 and 100.
Each node will have value between 0 and 100.
The given tree is a binary search tree.

题解：

仔细观察这棵树，实际上是一个先右节点，再当前节点，再左节点的“中序”遍历顺序，即可满足要求。

没做好的一点是用了一个外面的变量sum，其实应该是可以不用的。

代码：

class Solution {
int sum=0;
public:
    TreeNode* bstToGst(TreeNode* root) {
        if(root->right)
        {
            root->right=bstToGst(root->right);
        }    
        sum+=root->val;
        root->val=sum;
        if(root->left)
        {
           root->left=bstToGst(root->left);            
        }
        return root;
    }
};

版权声明：本文来源CSDN，感谢博主原创文章，遵循 CC 4.0 by-sa 版权协议，转载请附上原文出处链接和本声明。
原文链接：https://blog.csdn.net/David_Jett/article/details/92800197
站方申明：本站部分内容来自社区用户分享，若涉及侵权，请联系站方删除。

发表于 2023-01-02 09:08:49
阅读 ( 263 )
分类：算法

【刷leetcode，拿Offer-019】1038. Binary Search Tree to Greater Sum Tree

你可能感兴趣的文章

精选的优质文章

0 条评论

官方社群

GO教程

推荐文章

猜你喜欢

随便看看