[LeetCode] 1038. Binary Search Tree to Greater Sum Tree

[grandyang]

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 同步地址:

#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 题目讲解汇总(持续更新中...)