1382. Balance a Binary Search Tree 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
    public TreeNode balanceBST(TreeNode root) {
        // left -> root -> right

        List<TreeNode> treeNodeIncreaseList = new ArrayList<>();
        dfs(root, treeNodeIncreaseList);

        int startIndex = 0, endIndex = treeNodeIncreaseList.size() - 1;
        return buildBalanceBST(treeNodeIncreaseList, startIndex, endIndex);
    }

    private TreeNode buildBalanceBST(List<TreeNode> treeNodeIncreaseList, int startIndex, int endIndex) {
        if (startIndex > endIndex) {
            return null;
        }

        int midIndex = (startIndex + endIndex) >>> 1;
        TreeNode root = treeNodeIncreaseList.get(midIndex);
        root.left = buildBalanceBST(treeNodeIncreaseList, startIndex, midIndex - 1);
        root.right = buildBalanceBST(treeNodeIncreaseList, midIndex + 1, endIndex);
        return root;
    }

    private void dfs(TreeNode node, List<TreeNode> treeNodeIncreaseList) {
        if (node == null) {
            return;
        }

        dfs(node.left, treeNodeIncreaseList);
        treeNodeIncreaseList.add(node);
        dfs(node.right, treeNodeIncreaseList);
    }
}

References

1382. Balance a Binary Search Tree