题目
给定一个二叉搜索树（Binary Search Tree），把它转换成为累加树（Greater Tree)，使得每个节点的值是原来的节点值加上所有大于它的节点值之和。
注意：本题和LeetCode.1038相同
题目分析
已知二叉搜索树通过中序遍历可以得到一个有序递增序列。那么如果我们按照右孩子->根节点->左孩子的方式去遍历树，就会得到一个有序递减序列。
逆中序遍历:
void unInOrder(tree root){
if (root == NULL) return NULL;
unInOrder(root->right);
visit(root->val);
unInOrder(root->left);
}
将遍历得到的结点值依次累加，就可以得到累加树。累加的过程:
int num = 0;
int unInOrder(tree root, int num){
if (root == NULL) return NULL;
num = unInOrder(root->right, num);
root->val += num;
num = root->val;
num = unInOrder(root->left, num);
return num;
}
题目解答
int unInOrder(struct TreeNode* root, int num){
if (root == NULL) return num;
num = unInOrder(root->right, num);
root->val += num;
num = root->val;
num = unInOrder(root->left, num);
return num;
}
struct TreeNode* convertBST(struct TreeNode* root){
if (root == NULL) return NULL;
unInOrder(root, 0);
return root;
}
