楼主:
JIWP (JIWP)
2024-06-26 17:28:191382. Balance a Binary Search Tree
给你一个二元搜寻树
想办法把它变成深度不相差超过1
思路:
先把所有节点的值由记录下来
再去做成题目要求的样子
太久没写BST，差点忘记要怎么写
写起来有够卡
golang code :
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func balanceBST(root *TreeNode) *TreeNode {
var arr []int
sortarray(root, &arr)
return dfs(arr)
}
func sortarray(node *TreeNode, arr *[]int) {
if node == nil {
return
}
sortarray(node.Left, arr)
*arr = append(*arr, node.Val)
sortarray(node.Right, arr)
}
func dfs(arr []int) *TreeNode {
if len(arr) == 0 {
return nil
}
res := &TreeNode{}
res.Val = arr[len(arr)/2]
res.Left = dfs(arr[:len(arr)/2])
res.Right = dfs(arr[len(arr)/2+1:])
return res
}