[Leetcode] Problem 1382 - Balance a Binary Search Tree

Posted on | In ,

Given a binary search tree, return a balanced binary search tree with the same node values.

A binary search tree is balanced if and only if the depth of the two subtrees of every node never differ by more than 1.

If there is more than one answer, return any of them.

Example

00LHv6.png

Input: root = [1,null,2,null,3,null,4,null,null]

Output: [2,1,3,null,null,null,4]

Explanation: This is not the only correct answer, [3,1,4,null,2,null,null] is also correct.

Constraints

The number of nodes in the tree is between 1 and 10^4.
The tree nodes will have distinct values between 1 and 10^5.

Code

1
2
3
4
5
6
7
8
9
10
11
12
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;
    }
}
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
public TreeNode balanceBST(TreeNode root) {
    List<Integer> nodes = new ArrayList<>();
    inorder(nodes, root);
    return traverse(nodes, 0, nodes.size() - 1);
}

private void inorder(List<Integer> nodes, TreeNode root) {
    if (root == null)
        return;

    inorder(nodes, root.left);
    nodes.add(root.val);
    inorder(nodes, root.right);
}

private TreeNode traverse(List<Integer> nodes, int begin, int end) {
    if (end < begin)
        return null;

    int idx = begin + (end - begin) / 2;
    TreeNode root = new TreeNode(nodes.get(idx));
    root.left = traverse(nodes, begin, idx - 1);
    root.right = traverse(nodes, idx + 1, end);
    return root;
}