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
class Solution { public: TreeNode* convertBST(TreeNode* root) { int sum = 0; convertBSTcore(root, sum); return root; } void convertBSTcore(TreeNode* root, int& sum) { if (root == nullptr) return; convertBSTcore(root->right, sum); root->val += sum; sum = root->val; convertBSTcore(root->left, sum); } }; // 36 ms
用迭代完成该过程。
class Solution { public: TreeNode* convertBST(TreeNode* root) { if (root == nullptr) return 0; int sum = 0; stack<TreeNode*> s; TreeNode* node = root; while (node != nullptr || !s.empty()) { while (node != nullptr) { s.push(node); node = node->right; } node = s.top(); s.pop(); node->val += sum; sum = node->val; node = node->left; } return root; } }; // 35 ms
[LeetCode] Convert BST to Greater Tree
原文：http://www.cnblogs.com/immjc/p/7147857.html