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

import java.util.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

class Solution {
    public TreeNode convertBST(TreeNode root) {
        accumulate(root, 0);
        return root;
    }

    private int accumulate(TreeNode node, int sum) {
        if (node == null) return sum;
        sum = accumulate(node.right, sum);
        sum += node.val;
        node.val = sum;
        return accumulate(node.left, sum);
    }
}