Sponsored
Sponsored
This approach involves performing an in-order traversal of the binary search tree to collect its node values in sorted order. Since the values are sorted, we can then use the sorted list to construct a balanced binary search tree. The central idea is that the middle element of the sorted list becomes the root of the tree, and recursively the middle element of each sublist becomes the root of the subtrees, thereby ensuring balanced condition.
Time Complexity: O(n), where n is the number of nodes in the BST, for the in-order traversal and subsequent tree construction.
Space Complexity: O(n), for storing the node values in an array.
1import java.util.*;
2
3class TreeNode {
4 int val;
5 TreeNode left;
6 TreeNode right;
7 TreeNode(int x) { val = x; }
8}
9
10public class Solution {
11 private void inorder(TreeNode root, List<Integer> nodes) {
12 if (root == null) return;
13 inorder(root.left, nodes);
14 nodes.add(root.val);
15 inorder(root.right, nodes);
16 }
17
18 private TreeNode buildTree(List<Integer> nodes, int start, int end) {
19 if (start > end) return null;
20 int mid = start + (end - start) / 2;
21 TreeNode node = new TreeNode(nodes.get(mid));
22 node.left = buildTree(nodes, start, mid - 1);
23 node.right = buildTree(nodes, mid + 1, end);
24 return node;
25 }
26
27 public TreeNode balanceBST(TreeNode root) {
28 List<Integer> nodes = new ArrayList<>();
29 inorder(root, nodes);
30 return buildTree(nodes, 0, nodes.size() - 1);
31 }
32}The Java solution follows the identical logic as the C++ and C versions, using an ArrayList to collect BST values in sorted order, then constructs the balanced tree using a recursive approach.
This alternative approach aims to build a balanced BST directly from the given BST by using a divide-and-conquer strategy. The process involves using in-order traversal to fetch node values, converting it to a sorted array, and recursively constructing the entire balanced tree directly. While the initial step is similar, this approach focuses on minimizing operations by targeting balanced construction upfront.
Time Complexity: O(n), anchored in initial traversal and full reconstruction.
Space Complexity: O(n), stemming from node value arrays.
The Python code brings forth similar functional elements. In-order traversal supports sorted collection, forwarded to createBalancedTree for balanced structural outcomes guided by midpoints.