1382. 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
}