LeetCode笔记：538. Convert BST to G

问题（Easy）：

Given 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.

Example:

Input: The root of a Binary Search Tree like this:

Output: The root of a Greater Tree like this:

大意：

给出一个二叉搜索树（BST），将其转换为更大树，即原本BST中每个节点值都转换为其加上树中所有比它大的节点值之和。

例子：

输入：二叉搜索树如下：

输出：更大树如下：

思路：

题目的意思是节点中每个值，都把树中所有比它大的值加起来并加上它自己，就是它的新值。

这肯定要遍历整个树才知道有哪些比一个节点值大的数。因为节点的位置还不能变，所以只能直接在树上操作，这里就要用到二叉搜索树的性质：右大左小。

我们用遍历。

对于每个节点，比它大的节点有：父节点、父节点的右子节点树上所有节点、自己的右子节点、自己的右子节点树上所有节点。所以我们在计算一个节点的新值时，需要把所有这些值都加起来作为自己的新值。

而对于一个节点的左子节点，我们需要将上面算出来的新值给左子节点，这样就是左子节点的“父节点及父节点的右子节点树上所有节点值之和”了。

对于一个节点的右子节点，我们需要将“父节点及父节点的右子节点树上所有节点值之和”给右子节点，因为对于右子节点，它父节点的父节点，及那个节点的右子树，一定都比它大。这里和左子节点给的值其实就不一样了，需要区分计算并供给。

这样我们就可以对每一个节点进行操作，并组成一个递归操作了。

代码（C++）：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int sumValue(TreeNode* root, int toLeft) {
        int sum = root->val;
        root->val += toLeft;
        if (root->right){
            int rightValue = sumValue(root->right, toLeft);
            root->val += rightValue;
            sum += rightValue;
        }
        if (root->left) {
            int leftValue = sumValue(root->left, root->val);
            sum += leftValue;
        }
        return sum;
    }
    
    TreeNode* convertBST(TreeNode* root) {
        if (!root) return root;
        int temp = sumValue(root, 0);
        return root;
    }
};

他山之石：

其实上面的思路可以再简化一下，先从最大的节点，也就是最右叶子节点开始算，往回退，并用一个全局变量保存一个和，从右子节点，算到节点本身，再算到左子节点，代码简单很多，但是逻辑需要想清楚。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
private:
    int cur_sum = 0;
public:
    void travel(TreeNode* root){
        if (!root) return;
        if (root->right) travel(root->right);
        
        root->val = (cur_sum += root->val);
        if (root->left) travel(root->left);
    }
    TreeNode* convertBST(TreeNode* root) {
        travel(root);
        return root;
    }
};

合集：https://github.com/Cloudox/LeetCode-Record

查看作者首页