LeetCode Convert BST to Greater Tree 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:
              5
            /   \
           2     13
Output: The root of a Greater Tree like this:
             18
            /   \
          20     13

---

给定一棵二叉搜索树，要求把每个点的值换成BST中大于等于该点的其他所有点的值之和。 很有意思的一个题，因为BST满足左<=根<=右，则比某个点大的点在其根节点和右兄弟上，为了得到根节点和右兄弟节点之和，可以采用右->根->左的遍历顺序，也就是和先序遍历正好相反的顺序遍历BST，同时记录遍历过的数之和。 代码如下： [cpp] class Solution { private: void revPreOrder(TreeNode* root, int& sum) { if (root->right)revPreOrder(root->right, sum); sum += root->val; root->val = sum; if (root->left)revPreOrder(root->left, sum); } public: TreeNode* convertBST(TreeNode* root) { if (!root)return NULL; int sum = 0; revPreOrder(root, sum); return root; } }; [/cpp] 本代码提交AC，用时46MS。]]>