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

/*
 * 思路：
 * 1. 我们将树中的节点值存储到一个列表中。
 * 2. 对列表进行降序排序。
 * 3. 使用累加器计算节点值的前缀和。
 * 4. 使用哈希映射存储节点值及其对应的前缀和。
 * 5. 再次遍历树并更新节点值。
 */

import java.util.*;
import java.util.stream.Collectors;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    public TreeNode convertBST(TreeNode root) {
        if (root == null) return null;

        List<Integer> values = new ArrayList<>();
        inOrder(root, values);

        List<Integer> sortedValues = values.stream()
                                            .sorted(Comparator.reverseOrder())
                                            .collect(Collectors.toList());

        Map<Integer, Integer> prefixSumMap = new HashMap<>();
        int sum = 0;
        for (int value : sortedValues) {
            sum += value;
            prefixSumMap.put(value, sum);
        }

        updateValues(root, prefixSumMap);
        return root;
    }

    private void inOrder(TreeNode node, List<Integer> values) {
        if (node != null) {
            inOrder(node.left, values);
            values.add(node.val);
            inOrder(node.right, values);
        }
    }

    private void updateValues(TreeNode node, Map<Integer, Integer> prefixSumMap) {
        if (node != null) {
            updateValues(node.left, prefixSumMap);
            node.val = prefixSumMap.get(node.val);
            updateValues(node.right, prefixSumMap);
        }
    }
}