LeetCode笔记：538. Convert BST to Greater Tree
LeetCode笔记：538. Convert BST to Greater Tree
问题（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