package leetcode;

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

/**
 * https://leetcode.com/problems/balance-a-binary-search-tree/
 */
public class Problem1382 {
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

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

    public TreeNode balanceBST(TreeNode root) {
        List<TreeNode> nodes = new ArrayList<>();
        collectNodes(root, nodes);
        LinkedList<TreeNode> list = new LinkedList<>();
        int i = 0;
        list.add(nodes.get(i++));
        while (i < nodes.size()) {
            TreeNode current = list.getFirst();
            if (i < nodes.size()) {
                current.left = nodes.get(i++);
                list.add(current.left);
            }
            if (i < nodes.size()) {
                current.right = nodes.get(i++);
                list.add(current.right);
            }
        }
        return nodes.get(0);
    }

    private static void collectNodes(TreeNode root, List<TreeNode> nodes) {
        if (root == null) {
            return;
        }
        nodes.add(root);
        collectNodes(root.left, nodes);
        collectNodes(root.right, nodes);
    }

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

@@ -44,37 +44,8 @@
 st;%0A
-import java.util.LinkedList;%0A
 impo
@@ -314,24 +314,117 @@
 x;%0A        %7D
+%0A%0A        @Override%0A        public String toString() %7B%0A            return %22%22 + val;%0A        %7D
 %0A    %7D%0A%0A    
@@ -564,273 +564,195 @@
     
-LinkedList%3C
+return build
 Tree
-Node%3E list = new LinkedList%3C%3E(
+(nodes, 0, nodes.size() - 1
 );%0A    
+%7D%0A%0A
     
-int i = 0;%0A        list.add(nodes.get(i++));%0A        while (i %3C nodes.size()) %7B%0A            TreeNode current = list.getFirst();%0A            if (i %3C nodes.size()) %7B%0A                current.left = nodes.get(i++)
+private static TreeNode buildTree(List%3CTreeNode%3E nodes, int left, int right) %7B%0A        if (left %3E right) %7B%0A            return null
 ;%0A  
@@ -753,32 +753,34 @@
 ll;%0A        
+%7D%0A
         
 list.add(cur
@@ -771,194 +771,203 @@
     
-list.add(current.left);%0A            %7D%0A            if (i %3C nodes.size()) %7B%0A                current.right = nodes.get(i++);%0A                list.add(current.right);%0A            %7D%0A        %7D
+int mid = (left + right) / 2;%0A        TreeNode node = new TreeNode(nodes.get(mid).val);%0A        node.left = buildTree(nodes, left, mid - 1);%0A        node.right = buildTree(nodes, mid + 1, right);
 %0A   
@@ -986,16 +986,8 @@
 node
-s.get(0)
 ;%0A  
@@ -1129,33 +1129,8 @@
   %7D%0A
-        nodes.add(root);%0A
     
@@ -1157,32 +1157,57 @@
 t.left, nodes);%0A
+        nodes.add(root);%0A
         collectN
@@ -1240,105 +1240,7 @@
    %7D
-%0A%0A    public static void main(String%5B%5D args) %7B%0A        Problem1382 prob = new Problem1382();%0A    %7D
 %0A%7D%0A

Solve problem 1382