# Flatten to list, compute "great value", then map back values to the tree

• private LinkedList<Integer> flat(TreeNode root)
{
LinkedList<Integer> r = new LinkedList<>();
if (root == null)
return r;
List<Integer> lr = flat(root.right);
r.addAll(lr);
r.add(root.val);
List<Integer> ll = flat(root.left);
r.addAll(ll);
return r;
}
Map<Integer, Integer> m = new HashMap<>();

private void traverse(TreeNode root)
{
if (root == null)
return;
root.val = m.get(root.val);
traverse(root.left);
traverse(root.right);
}

`````` public TreeNode convertBST(TreeNode root) {
LinkedList<Integer> ll = flat(root);

Iterator<Integer> i = ll.iterator();
int t = 0;
while (i.hasNext())
{
int v = i.next();
t += v;
m.put(v, t);
}
traverse(root);

return root;
}``````

• Another solution based on recursion and tree structure:

private int aux(TreeNode root, int parentVal)
{
if (root == null)
return 0;
int oldVal = root.val;
root.val += parentVal;
int rightVal = aux(root.right, parentVal);
root.val += rightVal;
int leftVal = aux(root.left, root.val);
return rightVal+leftVal+oldVal;
}
public TreeNode convertBST(TreeNode root) {
aux(root, 0);
return root;
}

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.