1382. Balance a Binary Search Tree.md

1382. Balance a Binary Search Tree

• takeway: always pick middle element to build tree recursively since we want to balance the BST
• O(n) O(n)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode balanceBST(TreeNode root) {
        
        List<Integer> list = new ArrayList<>();
        fillList(root, list);
        
        //always pick middle when build tree
        int n = list.size();
        return buildBBST(list,0, n-1);// []
    }
    TreeNode buildBBST(List<Integer> list, int start, int end) {
        if(start>end) return null;
        int mid = start + (end-start)/2;
        TreeNode node = new TreeNode(list.get(mid));
        node.left = buildBBST(list, start, mid-1);
        node.right = buildBBST(list, mid+1, end);
        return node;
    }
    void fillList(TreeNode node, List<Integer> list) {
        if(node==null) return;
        fillList(node.left, list);
        list.add(node.val);
        fillList(node.right, list);
    }
}