leetcode problem 538 https://leetcode.com/problems/convert-bst-to-greater-tree/description/

naive.java

// This is the naive idea to serialize the tree into an array, modify the values, but keep the left/right child
// intact, but this uses extra O(N) space and O(N) time
public void serializeTreeSum(TreeNode node) {
    List<TreeNode> nodes = new ArrayList<>();
    this.inorderTraversal(node, nodes);

    // nodes is sorted ascendingly after inorder traversal, keep a rolling sum
    int rollingSum = 0;
    for (int i = nodes.size() - 1; i >= 0; i--) {
        nodes.get(i).val = nodes.get(i).val + rollingSum;
        rollingSum = nodes.get(i).val;
    }
}

public void inorderTraversal(TreeNode node, List<TreeNode> nodes) {
    if (node == null) {
        return;
    }

    this.inorderTraversal(node.left, nodes);
    nodes.add(node);
    this.inorderTraversal(node.right, nodes);
}

public TreeNode convertBST(TreeNode root) {
    this.serializeTreeSum(root);
    return root;
}