package leetcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * https://leetcode.com/problems/convert-bst-to-greater-tree/
 */
public class Problem538 {
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    public TreeNode convertBST(TreeNode root) {
        if (root == null) {
            return root;
        }
        List<Integer> list = new ArrayList<>();
        sortedList(root, list);
        int sum = 0;
        int[] sums = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            sum += list.get(i);
            if (i == 0) {
                sums[i] = 0;
            } else {
                sums[i] = sums[i - 1] + list.get(i - 1);
            }
        }
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < list.size(); i++) {
            if (i == 0) {
                map.put(list.get(i), sum);
            } else {
                map.put(list.get(i), sum - sums[i]);
            }
        }
        return convert(root, map);
    }

    private static TreeNode convert(TreeNode node, Map<Integer, Integer> map) {
        TreeNode left = null;
        TreeNode right = null;
        if (node.left == null && node.right == null) {
            return new TreeNode(map.get(node.val));
        }
        if (node.left != null) {
            left = convert(node.left, map);
        }
        if (node.right != null) {
            right = convert(node.right, map);
        }
        TreeNode parent = new TreeNode(map.get(node.val));
        parent.left = left;
        parent.right = right;
        return parent;
    }

    private static void sortedList(TreeNode node, List<Integer> list) {
        if (node == null) {
            return;
        }
        sortedList(node.left, list);
        list.add(node.val);
        sortedList(node.right, list);
    }
}

@@ -16,108 +16,8 @@
 e;%0A%0A
-import java.util.ArrayList;%0Aimport java.util.HashMap;%0Aimport java.util.List;%0Aimport java.util.Map;%0A%0A
 /**%0A
@@ -395,682 +395,102 @@
     
-List%3CInteger%3E list = new ArrayList%3C%3E();%0A        sortedList(root, list);%0A        int sum = 0;%0A        int%5B%5D sums = new int%5Blist.size()%5D;%0A        for (int i = 0; i %3C list.size(); i++) %7B%0A            sum += list.get(i);%0A            if (i == 0) %7B%0A                sums%5Bi%5D = 0;%0A            %7D else %7B%0A                sums%5Bi%5D = sums%5Bi - 1%5D + list.get(i - 1);%0A            %7D%0A        %7D%0A        Map%3CInteger, Integer%3E map = new HashMap%3C%3E();%0A        for (int i = 0; i %3C list.size(); i++) %7B%0A            if (i == 0) %7B%0A                map.put(list.get(i), sum);%0A            %7D else %7B%0A                map.put(list.get(i), sum - sums%5Bi%5D);%0A            %7D%0A        %7D%0A        return convert(root, map)
+return convert(root, new Sum());%0A    %7D%0A%0A    private static class Sum %7B%0A        private int val
 ;%0A  
@@ -549,33 +549,15 @@
 de, 
-Map%3CInteger, Integer%3E map
+Sum sum
 ) %7B%0A
@@ -568,60 +568,54 @@
     
-TreeNode 
+if (node.
 left =
+=
  null
-;%0A        TreeNode 
+ && node.
 right =
+=
  null
-;
+) %7B
 %0A   
@@ -623,54 +623,32 @@
     
-if (node.left == null && node.right == null) %7B
+    sum.val += node.val;
 %0A   
@@ -676,34 +676,24 @@
 reeNode(
-map.get(node
+sum
 .val)
-)
 ;%0A      
@@ -708,86 +708,30 @@
     
-if (node.lef
+TreeNode righ
 t 
-!
 = null
-) %7B%0A            left = convert(node.left, map);%0A        %7D
+;
 %0A   
@@ -801,19 +801,19 @@
 .right, 
-map
+sum
 );%0A     
@@ -829,55 +829,27 @@
     
-TreeNode parent = new TreeNode(map.get(
+sum.val += 
 node.val
 ));%0A
@@ -844,18 +844,16 @@
 node.val
-))
 ;%0A      
@@ -858,159 +858,56 @@
     
-parent.left = left;%0A        parent.right = right;%0A        return parent
+int val = sum.val
 ;%0A    
-%7D%0A%0A
     
-private static void sortedList(TreeNode node, List%3CInteger%3E list) %7B
+TreeNode left = null;
 %0A   
@@ -919,18 +919,23 @@
 if (node
- =
+.left !
 = null) 
@@ -952,127 +952,174 @@
     
-return;%0A        %7D%0A        sortedList(node.left, list);%0A        list.add(node.val);%0A        sortedList(node.right, list)
+left = convert(node.left, sum);%0A        %7D%0A        TreeNode parent = new TreeNode(val);%0A        parent.left = left;%0A        parent.right = right;%0A        return parent
 ;%0A  

Update problem 538