# 1382. Balance a Binary Search Tree
###### tags: `Leetcode` `FaceBook` `Medium` `Binary Search Tree` `Inorder Traversal`
Link: https://leetcode.com/problems/balance-a-binary-search-tree/
## 思路
InorderTraversal+Recursion build tree
## Code

class Solution {
    public TreeNode balanceBST(TreeNode root) {
        List<Integer> l = new ArrayList<>();
        inOrderTraversal(root, l);
        
        // root = new TreeNode(l.get(l.size/2));
        TreeNode newRoot = buildBST(l, 0, l.size()-1);
        return newRoot;
    }
    public void inOrderTraversal(TreeNode root, List<Integer> l){
        if(root==null) return;
        inOrderTraversal(root.left,l);
        l.add(root.val);
        inOrderTraversal(root.right,l);
    }
    public TreeNode buildBST(List<Integer> l, int start, int end){
        if(start>end) return null;
        if(start==end) return new TreeNode(l.get(start));
        int mid = (start+end)/2;
        TreeNode root = new TreeNode(l.get(mid));
        root.left = buildBST(l, start, mid-1);
        root.right = buildBST(l, mid+1, end);
        return root;
    }
}