import java.util.*;

/**

* 1382. Balance a Binary Search Tree

* Medium

*

* 60

*

* 12

*

* Add to List

*

* Share

* 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 1:

*

*

*

* 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.

* Accepted

* 5,827

* Submissions

* 7,846

* Seen this question in a real interview before?

*

* Yes

*

* No

* Contributor

* LeetCode

* 0 ~ 6 months6 months ~ 1 year1 year ~ 2 years

*

* Amazon

* |

* LeetCode

* Convert the tree to a sorted array using an in-order traversal.

* Construct a new balanced tree from the sorted array recursively.

*/

public class BalanceaBinarySearchTree {

class Solution {

List<TreeNode> sortedArr = new ArrayList<>();

public TreeNode balanceBST(TreeNode root) {

inorderTraverse(root);

return sortedArrayToBST(0, sortedArr.size() - 1);

}

void inorderTraverse(TreeNode root) {

if (root == null) return;

inorderTraverse(root.left);

sortedArr.add(root);

inorderTraverse(root.right);

}

TreeNode sortedArrayToBST(int start, int end) {

if (start > end) return null;

int mid = start + (end - start) / 2;

TreeNode root = sortedArr.get(mid);

root.left = sortedArrayToBST(start, mid - 1);

root.right = sortedArrayToBST(mid + 1, end);

return root;

}

}

}