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.
1#include <vector>
2using namespace std;
3
4struct TreeNode {
5 int val;
6 TreeNode *left;
7 TreeNode *right;
8 TreeNode(int x) : val(x), left(NULL), right(NULL) {}
9};
10
11void inorder(TreeNode* root, vector<int>& nodes) {
12 if (!root) return;
13 inorder(root->left, nodes);
14 nodes.push_back(root->val);
15 inorder(root->right, nodes);
16}
17
18TreeNode* buildTree(vector<int>& nodes, int start, int end) {
19 if (start > end) return nullptr;
20 int mid = start + (end - start) / 2;
21 TreeNode* node = new TreeNode(nodes[mid]);
22 node->left = buildTree(nodes, start, mid - 1);
23 node->right = buildTree(nodes, mid + 1, end);
24 return node;
25}
26
27TreeNode* balanceBST(TreeNode* root) {
28 vector<int> nodes;
29 inorder(root, nodes);
30 return buildTree(nodes, 0, nodes.size() - 1);
31}The C++ solution employs the same concept as the C solution, using a vector to store the node values obtained from an in-order traversal. The buildTree function recursively constructs the tree using the midpoint of the list as the root for each subtree.
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.
using System.Collections.Generic;
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) { val = x; }
}
public class Solution {
private void Inorder(TreeNode root, List<int> nodes) {
if (root == null) return;
Inorder(root.left, nodes);
nodes.Add(root.val);
Inorder(root.right, nodes);
}
private TreeNode CreateBalancedTree(List<int> nodes, int start, int end) {
if (start > end) return null;
int mid = start + (end - start) / 2;
TreeNode node = new TreeNode(nodes[mid]);
node.left = CreateBalancedTree(nodes, start, mid - 1);
node.right = CreateBalancedTree(nodes, mid + 1, end);
return node;
}
public TreeNode BalanceBST(TreeNode root) {
List<int> nodes = new List<int>();
Inorder(root, nodes);
return CreateBalancedTree(nodes, 0, nodes.Count - 1);
}
}C# scripting follows familiar patterns. With an Inorder sweep yielding a number-list, value-mediated trials center on CreateBalancedTree for balance-optimized BST formation.