問(wèn)題（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:
大意：
給出一個(gè)二叉搜索樹(shù)（BST），將其轉(zhuǎn)換為更大樹(shù)，即原本BST中每個(gè)節(jié)點(diǎn)值都轉(zhuǎn)換為其加上樹(shù)中所有比它大的節(jié)點(diǎn)值之和。
例子：
輸入：二叉搜索樹(shù)如下：
輸出：更大樹(shù)如下：
思路：
題目的意思是節(jié)點(diǎn)中每個(gè)值，都把樹(shù)中所有比它大的值加起來(lái)并加上它自己，就是它的新值。
這肯定要遍歷整個(gè)樹(shù)才知道有哪些比一個(gè)節(jié)點(diǎn)值大的數(shù)。因?yàn)楣?jié)點(diǎn)的位置還不能變，所以只能直接在樹(shù)上操作，這里就要用到二叉搜索樹(shù)的性質(zhì)：右大左小。
我們用遍歷。
對(duì)于每個(gè)節(jié)點(diǎn)，比它大的節(jié)點(diǎn)有：父節(jié)點(diǎn)、父節(jié)點(diǎn)的右子節(jié)點(diǎn)樹(shù)上所有節(jié)點(diǎn)、自己的右子節(jié)點(diǎn)、自己的右子節(jié)點(diǎn)樹(shù)上所有節(jié)點(diǎn)。所以我們?cè)谟?jì)算一個(gè)節(jié)點(diǎn)的新值時(shí)，需要把所有這些值都加起來(lái)作為自己的新值。
而對(duì)于一個(gè)節(jié)點(diǎn)的左子節(jié)點(diǎn)，我們需要將上面算出來(lái)的新值給左子節(jié)點(diǎn)，這樣就是左子節(jié)點(diǎn)的“父節(jié)點(diǎn)及父節(jié)點(diǎn)的右子節(jié)點(diǎn)樹(shù)上所有節(jié)點(diǎn)值之和”了。
對(duì)于一個(gè)節(jié)點(diǎn)的右子節(jié)點(diǎn)，我們需要將“父節(jié)點(diǎn)及父節(jié)點(diǎn)的右子節(jié)點(diǎn)樹(shù)上所有節(jié)點(diǎn)值之和”給右子節(jié)點(diǎn)，因?yàn)閷?duì)于右子節(jié)點(diǎn)，它父節(jié)點(diǎn)的父節(jié)點(diǎn)，及那個(gè)節(jié)點(diǎn)的右子樹(shù)，一定都比它大。這里和左子節(jié)點(diǎn)給的值其實(shí)就不一樣了，需要區(qū)分計(jì)算并供給。
這樣我們就可以對(duì)每一個(gè)節(jié)點(diǎn)進(jìn)行操作，并組成一個(gè)遞歸操作了。
代碼（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;
}
};
他山之石：
其實(shí)上面的思路可以再簡(jiǎn)化一下，先從最大的節(jié)點(diǎn)，也就是最右葉子節(jié)點(diǎn)開(kāi)始算，往回退，并用一個(gè)全局變量保存一個(gè)和，從右子節(jié)點(diǎn)，算到節(jié)點(diǎn)本身，再算到左子節(jié)點(diǎn)，代碼簡(jiǎn)單很多，但是邏輯需要想清楚。
/**
* 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
