package leetcode;

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

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

    public TreeNode bstToGst(TreeNode root) {
        // TODO
        return null;
    }

    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); // 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
    }
}

@@ -12,16 +12,68 @@
 tcode;%0A%0A
+import java.util.ArrayList;%0Aimport java.util.List;%0A%0A
 public c
@@ -252,96 +252,1081 @@
   %7D%0A
-    %7D%0A%0A    public TreeNode bstToGst(TreeNode root) %7B%0A        // TODO%0A        return null
+%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);%0A        return bstToGst(root, sums, new IntRef());%0A    %7D%0A%0A    private static TreeNode bstToGst(TreeNode root, List%3CInteger%3E sums, IntRef idx) %7B%0A        if (root == null) %7B%0A            return null;%0A        %7D%0A        root.left = bstToGst(root.left, sums, idx);%0A        root.val = sums.get(sums.size() - 1) - sums.get(idx.val) + root.val;%0A        idx.val++;%0A        root.right = bstToGst(root.right, sums, idx);%0A        return root;%0A    %7D%0A%0A    private static class IntRef %7B%0A        private int val;%0A    %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  
@@ -1845,16 +1845,50 @@
 t(root);
+%0A        System.out.println(root);
  // 30%0A 

Update problem 1038