問題（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中每個節(jié)點值都轉換為其加上樹中所有比它大的節(jié)點值之和绣溜。
例子：
輸入：二叉搜索樹如下：
輸出：更大樹如下：
思路：
題目的意思是節(jié)點中每個值，都把樹中所有比它大的值加起來并加上它自己侮繁，就是它的新值。
這肯定要遍歷整個樹才知道有哪些比一個節(jié)點值大的數(shù)如孝。因為節(jié)點的位置還不能變宪哩，所以只能直接在樹上操作，這里就要用到二叉搜索樹的性質：右大左小第晰。
我們用遍歷锁孟。
對于每個節(jié)點，比它大的節(jié)點有：父節(jié)點茁瘦、父節(jié)點的右子節(jié)點樹上所有節(jié)點品抽、自己的右子節(jié)點、自己的右子節(jié)點樹上所有節(jié)點甜熔。所以我們在計算一個節(jié)點的新值時圆恤，需要把所有這些值都加起來作為自己的新值。
而對于一個節(jié)點的左子節(jié)點腔稀，我們需要將上面算出來的新值給左子節(jié)點盆昙，這樣就是左子節(jié)點的“父節(jié)點及父節(jié)點的右子節(jié)點樹上所有節(jié)點值之和”了羽历。
對于一個節(jié)點的右子節(jié)點，我們需要將“父節(jié)點及父節(jié)點的右子節(jié)點樹上所有節(jié)點值之和”給右子節(jié)點淡喜，因為對于右子節(jié)點秕磷，它父節(jié)點的父節(jié)點，及那個節(jié)點的右子樹炼团，一定都比它大澎嚣。這里和左子節(jié)點給的值其實就不一樣了，需要區(qū)分計算并供給们镜。
這樣我們就可以對每一個節(jié)點進行操作币叹，并組成一個遞歸操作了。
代碼（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;
}
};
他山之石：
其實上面的思路可以再簡化一下模狭，先從最大的節(jié)點颈抚，也就是最右葉子節(jié)點開始算，往回退嚼鹉，并用一個全局變量保存一個和贩汉，從右子節(jié)點，算到節(jié)點本身锚赤，再算到左子節(jié)點匹舞，代碼簡單很多，但是邏輯需要想清楚线脚。
/**
* 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
