二叉查找树转换为较大树

Leetcode 538
已知一个二叉查找树，将它转换为一个较大树，即所有的二叉查找树的节点，赋值为该节点本身的值与该节点大的节点的值的和

思考与分析

较大树中的节点与二叉树的节点一一对应，对于任意二叉查找树节点，需要将大于该节点的节点值累加到该节点上。暴力的方法是，对于每个节点，进行整棵树的遍历，将比它大的节点值进行累加，时间复杂度为O(n²)

思考

按照怎么样的方式，就可以在一次遍历整棵树的情况下，对节点值进行累加，当完成整棵树的遍历后，全部节点完成修改，整体时间复杂度O(n)

算法设计

修改中序遍历二叉树，先遍历二叉树右子树，再遍历该节点本身，最后遍历二叉树左子树，在中序遍历节点的时候将节点的值累加到全局变量sum中，在中序遍历时修改节点的值为sum.

void travel_tree(TreeNode *node, int &sum){
    if(!node){
        return;
    }
    travel_tree(node->right,sum);
    sum = sum + node->val;
    node->val = sum;
    travel_tree(node->left,sum);
}
class Solution{
public:
    TreeNode *convertBST(TreeNode *root){
        int sum = 0; 
        travel_tree(root, sum);
        return root;
    }
};