Leetcode Note: Go - Convert Sorted Array to Binary Search Tree
Convert Sorted Array to Binary Search Tree - LeetCode
https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/
- Go 言語で取り組んだメモ
所感
- わからん
実装準備
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func sortedArrayToBST(nums []int) *TreeNode {
}回答
Golang simple recursive solution - LeetCode Discuss
https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/discuss/964815/Golang-simple-recursive-solution
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func sortedArrayToBST(nums []int) *TreeNode {
if len(nums) == 0 {
return nil
}
mid := (len(nums)-1)/2
node := &TreeNode{}
node.Val = nums[mid]
node.Left = sortedArrayToBST(nums[:mid])
node.Right = sortedArrayToBST(nums[mid+1:])
return node
}- mid で中心を取得
- 中心を root node として Left, Right をソートするよう再帰
- height-balanced binary search tree という概念が難しい