package leetcode;

import java.util.ArrayList;
import java.util.List;

public class Problem1038 {
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }

        @Override
        public String toString() {
            return "" + val;
        }
    }

    public TreeNode bstToGst(TreeNode root) {
        List<Integer> sums = new ArrayList<>();
        traverse(root, sums);
        return bstToGst(root, sums, new IntRef());
    }

    private static TreeNode bstToGst(TreeNode root, List<Integer> sums, IntRef idx) {
        if (root == null) {
            return null;
        }
        root.left = bstToGst(root.left, sums, idx);
        root.val = sums.get(sums.size() - 1) - sums.get(idx.val) + root.val;
        idx.val++;
        root.right = bstToGst(root.right, sums, idx);
        return root;
    }

    private static class IntRef {
        private int val;
    }

    private static void traverse(TreeNode root, List<Integer> sums) {
        if (root == null) {
            return;
        }
        traverse(root.left, sums);
        if (sums.isEmpty()) {
            sums.add(root.val);
        } else {
            sums.add(sums.get(sums.size() - 1) + root.val);
        }
        traverse(root.right, sums);
    }

    public static void main(String[] args) {
        Problem1038 prob = new Problem1038();

        TreeNode root = new TreeNode(4);
        root.left = new TreeNode(1);
        root.left.left = new TreeNode(0);
        root.left.right = new TreeNode(2);
        root.left.right.right = new TreeNode(3);
        root.right = new TreeNode(6);
        root.right.left = new TreeNode(5);
        root.right.right = new TreeNode(7);
        root.right.right.right = new TreeNode(8);

        root = prob.bstToGst(root);
        System.out.println(root); // 30
        System.out.println(root.left); // 36
        System.out.println(root.left.left); // 36
        System.out.println(root.left.right); // 35
        System.out.println(root.left.right.right); // 33
        System.out.println(root.right); // 21
        System.out.println(root.right.left); // 26
        System.out.println(root.right.right); // 15
        System.out.println(root.right.right.right); // 8
    }
}

@@ -16,60 +16,8 @@
 e;%0A%0A
-import java.util.ArrayList;%0Aimport java.util.List;%0A%0A
 publ
@@ -200,231 +200,60 @@
   %7D%0A
-%0A        @Override%0A        public String toString() %7B%0A            return %22%22 + val;%0A        %7D%0A    %7D%0A%0A    public TreeNode bstToGst(TreeNode root) %7B%0A        List%3CInteger%3E sums = new ArrayList%3C%3E();%0A        traverse(root, sums);
+    %7D%0A%0A    public TreeNode bstToGst(TreeNode root) %7B
 %0A   
@@ -278,22 +278,16 @@
 st(root,
- sums,
  new Int
@@ -357,38 +357,18 @@
 ot, 
-List%3CInteger%3E sums, IntRef idx
+IntRef sum
 ) %7B%0A
@@ -439,27 +439,28 @@
        root.
-lef
+righ
 t = bstToGst
@@ -469,23 +469,18 @@
 oot.
-lef
+righ
 t, sum
-s, idx
 );%0A 
@@ -490,66 +490,18 @@
     
-root.val = sums.get(sums.size() - 1) - sums.get(idx
+sum
 .val
-)
  +
+=
  roo
@@ -519,17 +519,26 @@
     
-idx
+root.val = sum
 .val
-++
 ;%0A  
@@ -540,36 +540,35 @@
 l;%0A        root.
-righ
+lef
 t = bstToGst(roo
@@ -573,24 +573,17 @@
 oot.
-righ
+lef
 t, sum
-s, idx
 );%0A 
@@ -677,1334 +677,7 @@
    %7D
-%0A%0A    private static void traverse(TreeNode root, List%3CInteger%3E sums) %7B%0A        if (root == null) %7B%0A            return;%0A        %7D%0A        traverse(root.left, sums);%0A        if (sums.isEmpty()) %7B%0A            sums.add(root.val);%0A        %7D else %7B%0A            sums.add(sums.get(sums.size() - 1) + root.val);%0A        %7D%0A        traverse(root.right, sums);%0A    %7D%0A%0A    public static void main(String%5B%5D args) %7B%0A        Problem1038 prob = new Problem1038();%0A%0A        TreeNode root = new TreeNode(4);%0A        root.left = new TreeNode(1);%0A        root.left.left = new TreeNode(0);%0A        root.left.right = new TreeNode(2);%0A        root.left.right.right = new TreeNode(3);%0A        root.right = new TreeNode(6);%0A        root.right.left = new TreeNode(5);%0A        root.right.right = new TreeNode(7);%0A        root.right.right.right = new TreeNode(8);%0A%0A        root = prob.bstToGst(root);%0A        System.out.println(root); // 30%0A        System.out.println(root.left); // 36%0A        System.out.println(root.left.left); // 36%0A        System.out.println(root.left.right); // 35%0A        System.out.println(root.left.right.right); // 33%0A        System.out.println(root.right); // 21%0A        System.out.println(root.right.left); // 26%0A        System.out.println(root.right.right); // 15%0A        System.out.println(root.right.right.right); // 8%0A    %7D
 %0A%7D%0A

Solve problem 1038