【leetcode刷题】T141-把二叉搜索树转化成更大的树

例如：
输入: 二叉搜索树:
              5
            /   \
           2     13
输出: 转换为累加树:
             18
            /   \
          20     13

# 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.cur_sum = 0
        self.get_sum(root)
        return root

    def get_sum(self, node):
        if not node:
            return
        self.get_sum(node.right)
        node.val += self.cur_sum
        self.cur_sum = node.val
        self.get_sum(node.left)

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* convertBST(TreeNode* root) {
        int sum = 0;
        get_sum(root, sum);
        return root;
    }

    void get_sum(TreeNode* node, int& sum){
        if(!node)
            return;
        get_sum(node->right, sum);
        node->val += sum;
        sum = node->val;
        get_sum(node->left, sum);
    }
};