Given the root of a binary search tree, return a balanced binary search tree with the same node values. If there is more than one answer, return any of them.
A binary search tree is balanced if the depth of the two subtrees of every node never differs by more than 1.
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] is also correct.
Example 2:
Input: root = [2,1,3]
Output: [2,1,3]
Constraints:
The number of nodes in the tree is in the range [1, 104].
1 <= Node.val <= 105
Solutions
Solution 1: In-order Traversal + Construct Balanced Binary Search Tree
Since the original tree is a binary search tree, we can save the result of the in-order traversal in an array $nums$. Then we design a function $build(i, j)$, which is used to construct a balanced binary search tree within the index range $[i, j]$ in $nums$. The answer is $build(0, |nums| - 1)$.
The execution logic of the function $build(i, j)$ is as follows:
If $i > j$, then the balanced binary search tree is empty, return an empty node;
Otherwise, we take $mid = (i + j) / 2$ as the root node, then recursively build the left and right subtrees, and return the root node.
The time complexity is $O(n)$, and the space complexity is $O(n)$. Where $n$ is the number of nodes in the binary search tree.
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */funcbalanceBST(root*TreeNode)*TreeNode{ans:=[]int{}vardfsfunc(*TreeNode)dfs=func(root*TreeNode){ifroot==nil{return}dfs(root.Left)ans=append(ans,root.Val)dfs(root.Right)}varbuildfunc(i,jint)*TreeNodebuild=func(i,jint)*TreeNode{ifi>j{returnnil}mid:=(i+j)>>1left:=build(i,mid-1)right:=build(mid+1,j)return&TreeNode{Val:ans[mid],Left:left,Right:right}}dfs(root)returnbuild(0,len(ans)-1)}