LeetCode 1382. Balance a Binary Search Tree

Question

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

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.

Solution

先中序遍历得到有序的序列，然后构建BST。

Code

// time:O(n) space:O(n)
List<Integer> list;
    
    public TreeNode balanceBST(TreeNode root) {
        if (root == null) return null;
        list = new ArrayList<>();
        dfs(root);
        return build(list, 0, list.size() - 1);
    }
    
    public void dfs(TreeNode root) {
        if (root == null) return;
        dfs(root.left);
        list.add(root.val);
        dfs(root.right);
    }
    
    public TreeNode build(List<Integer> list, int left, int right) {
        if (left > right) return null;
        int mid = left + (right - left) / 2;
        TreeNode root = new TreeNode(list.get(mid));
        root.left = build(list, left, mid - 1);
        root.right = build(list, mid + 1, right);
        return root;
    }