Balance a Binary Search Tree LeetCode solution in Java

1
class Solution {
2
  public TreeNode balanceBST(TreeNode root) {
3
    List<Integer> arr = new ArrayList();
4
    InOrder(root, arr);
5
    return sortedArrayToBST(arr, 0, arr.size() - 1);
6
  }
7

8
  public void InOrder(TreeNode node, List<Integer> arr) {
9
    if (node != null) {
10
      InOrder(node.left, arr);
11
      arr.add(node.val);
12
      InOrder(node.right, arr);
13
    }
14
  }
15

16
  public TreeNode sortedArrayToBST(List<Integer> arr, int start, int end) {
17

18
    if (start > end) {
19
      return null;
20
    }
21

22
    int mid = (start + end) / 2;
23

24
    TreeNode node = new TreeNode(arr.get(mid));
25
    node.left = sortedArrayToBST(arr, start, mid - 1);
26
    node.right = sortedArrayToBST(arr, mid + 1, end);
27

28
    return node;
29
  }
30
}