1038. Binary Search Tree to Greater Sum Tree

Given the root of a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus sum of all keys greater than the original key in BST.

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.

Note: This question is the same as 538: https://leetcode.com/problems/convert-bst-to-greater-tree/

Example 1:

Input: root = [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]

Example 2:

Input: root = [0,null,1]
Output: [1,null,1]

Example 3:

Input: root = [1,0,2]
Output: [3,3,2]

Example 4:

Input: root = [3,2,4,1]
Output: [7,9,4,10]

Constraints:

  • The number of nodes in the tree is in the range [1, 100].
  • 0 <= Node.val <= 100
  • All the values in the tree are unique.
  • root is guaranteed to be a valid binary search tree.

这道题让我们将一棵二叉搜索树 Binary Search Tree 转为一棵较大树,跟之前那道题 Convert BST to Greater Tree 一模一样,博主不知道出这道题的意义是什么,连背景不换的,LeetCode 为啥还允许完全一样的题目存在,难道是强行帮我们复习之前的题目么?不管了,权当是复习吧。题目中说变为新的较大树的方法是,将 BST 中的每个结点值都加上所有大于其的结点值,由于 BST 的特点是左子结点值小于根结点值,小于右子结点值,则整个 BST 中最大的结点值应该在最右子结点,由于没有再比它更大的了,所以它不用再加上其他的结点值。其根结点值是第二大的结点值,需要加上该右子结点值。该根结点的左子结点(存在的话)就是第三大的结点值,需要加上更新后的根结点值。眼尖的童鞋应该已经看出来了,这个顺序其实就是颠倒后的中序遍历,正常的中序遍历是左根右,这里是右根左,不过没关系,用递归还是一样的简单。这里用一个变量 cur 来记录当前的结点值之和,作为递归函数的一个引用参数。在递归函数中,先判空,然后对右子结点调用递归函数,之后将 cur 值加到当前结点上面,然后更新 cur 值为当前结点值,然后再对左子结点调用递归函数即可,参见代码如下:

class Solution {
public:
    TreeNode* bstToGst(TreeNode* root) {
        int cur = 0;
        helper(root, cur);
        return root;
    }
    void helper(TreeNode*& node, int& cur) {
        if (!node) return;
        helper(node->right, cur);
        node->val += cur;
        cur = node->val;
        helper(node->left, cur);
    }
};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1038

类似题目:

Convert BST to Greater Tree

参考资料:

https://leetcode.com/problems/binary-search-tree-to-greater-sum-tree/

https://leetcode.com/problems/binary-search-tree-to-greater-sum-tree/discuss/286725/JavaC%2B%2BPython-Revered-Inorder-Traversal

https://leetcode.com/problems/binary-search-tree-to-greater-sum-tree/discuss/286906/Java-3-iterative-and-recursive-codes-w-comments-and-explanation.

LeetCode All in One 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

×

Help us with donation