1382. Balance a Binary Search Tree

Problem Statement

Pattern:

---

Trivial Solutions

ArrayList<TreeNode> list = new ArrayList<>();
 
void inorder(TreeNode root) {
	if(root == null) return; 
	inorder(root.left);
	list.add(root);
	inorder(root.right);
}
 
TreeNode balance(int start, int end) {
	if(start > end) return null;
	
	int mid = (end-start)/2 + start;
	TreeNode node = list.get(mid);
	
	node.left = balance(start, mid-1);
	node.right = balance(mid+1, end);
	
	return node;
}
 
public TreeNode balanceBST(TreeNode root) {
	inorder(root);
	return balance(0, list.size()-1);
}

DWS Solution

todoleetcode C++/Java with picture, DSW O(n)|O(1) - LeetCode Discuss