leetcode 538 Convert BST to Greater Tree

node->val += lsum + t 就会修改正在遍历的 node 的 val 值。

因为每个节点要添加上比他大的所有 key 的值，而一部分比他大的所有的 key 的值都在他的右子树上，所以我们在 dfs 的过程中直接统计所有子树的元素和就是很自然的了。我的 dfs 的返回值就是以 root 为根的子树的元素和。

（P.S. 我的代码的 lsum 和 rsum 竟然写反了，让我琢磨了好半天... = =）

==========

你想返回结果的根是可以的，但因为在遍历的时候我们也需要每个子树的元素和，相当于遍历的过程中，我们需要两个返回结果，我们只需要把这两个返回结果打一个包返回就好。在 C++ 中可以是用 pair，在 Java 中可以自己创建一个新的类承载多个元素。更一般的，如果我们在 dfs 的过程中需要得到子树的多个结果，把多个结果一起打一个包返回就好。（对于这一点，直接支持多返回值的语言就会显得更方便，比如 Python）

这里是我的参考代码：https://github.com/liuyubobobo/Play-Leetcode/blob/master/0501-1000/0538-Convert-BST-to-Greater-Tree/cpp-0538/main2.cpp

但其实，对于这个问题，由于遍历的过程中根本没有改变树的结果，只是改变树的节点的值，返回节点是没必要的（返回的节点肯定是传来的 node）

==========

另外，对于这个问题，其实我们还可以使用一个全局变量（在类中就是积累的成员变量）来记录当前遍历的所有节点的和。我们在 dfs 的时候可以每次先遍历右子树，再遍历左子树，也就是先找元素从大到小遍历。这样每次到一个 node 的时候，中序的位置，sum 中就是比当前 node 更大的所有元素的和。

我的参考代码：https://github.com/liuyubobobo/Play-Leetcode/blob/master/0501-1000/0538-Convert-BST-to-Greater-Tree/cpp-0538/main3.cpp

不过其实我不是特别喜欢设立这种算法相关的全局变量，所以看你的个人喜好了。（这种方式本身在很多编程实践中也不推荐使用，比如函数式编程。）

继续加油！：）