leetcode 538 把二叉搜索树转换为累加树

我最开始想的是中序遍历，在倒序求和，当前节点值加之前和即可。

后来看了下评论，用的是 右 - 中 - 左 的顺序遍历，但代码俺写不出来，卡死在和的维持上面。

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):

   def convertBST(self, root):
       """
       :type root: TreeNode
       :rtype: TreeNode
       """

       self.sum_= 0
       self.dfs(root)
       return root

   def dfs(self, root):
       if not root:
           return
       self.dfs(root.right)
       root.val += self.sum_
       self.sum_ = root.val
       self.dfs(root.left)

递归格式化，套出自己的写法，刻不容缓啊！！！