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.

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.

1
2
3
4
5
6
7
8
9
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

AVL? Too complicated.

思路: 本来就是BST就是要balance，所以就是要找到所有节点中间的median，作为root，然后recursively build其他的节点。 因为本来BST对应的节点就是inorder的，所以中序遍历得到的array就是有序的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    List<Integer> sorted = new ArrayList<>();
    
    public TreeNode balanceBST(TreeNode root) {
        inorder(root);
        return arrToBST(0, sorted.size() - 1);
    }
    
    public void inorder(TreeNode root) {
        if (root == null) return;
        inorder(root.left);
        sorted.add(root.val);
        inorder(root.right);
    }
    
    public TreeNode arrToBST(int left, int right) {
        if (left > right) return null;
        int mid = left + (right - left) / 2;
        TreeNode node = new TreeNode(sorted.get(mid)); // build
        node.left = arrToBST(left, mid - 1); // left
        node.right = arrToBST(mid + 1, right);
        return node;
    }
}

实话说，这道题出的很好。我为自己做了不少BST的题，但是还是感觉并没有掌握感到非常烦躁。

BST的题:

Easy:

1
2
3
4
5
538. Convert BST to Greater tree
938. Range Sum BST
530. Minimum Absolute Difference in BST
653. Two Sum IV - Input is a BST
783. Minimum Difference between BST Nodes

Medium:

1
2
3
4
5
6
7
8
1214. Two Sum BSTs
450. Delete Node in BST
230. Kth Smallest Element in BST
449. Serialize & Deserialize BST
776. Split BST
333. Largest BST subtree
285. Inorder Successor BST
510. Inorder Successor BST II

Hard:

1
1373. Maximum Sum BST in BT