LeetCodeに毎日挑戦してみた 108. Convert Sorted Array to Binary Search Tree（Python、Go)
Leetcodeとは
leetcode.com
ソフトウェア開発職のコーディング面接の練習といえばこれらしいです。
合計1500問以上のコーデイング問題が投稿されていて、実際の面接でも同じ問題が出されることは多いらしいとのことです。
golang入門＋アルゴリズム脳の強化のためにgoとPythonで解いていこうと思います。(Pythonは弱弱だが経験あり)
24問目（問題108)
108. Convert Sorted Array to Binary Search Tree
問題内容
Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.
（日本語訳）
要素が昇順で並べ替えられている配列が与えられた場合、それを高さバランスのとれたBSTに変換します。
この問題では、高さバランスのとれた二分木は、すべてのノードの2つのサブツリーの深さが1を超えて異ならない二分木として定義されます。
Example:
Given the sorted array: [-10,-3,0,5,9],
One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:
0
/ \
-3 9
/ /
-10 5
考え方
バランスを取れた二分木にするために、真ん中の位置をmidとして決めます
midはleftとright(Len(nums))で決まります
rootが決まったらそこにleftとrightを作成していきます
解答コード
class Solution(object):
def sortedArrayToBST(self, nums):
def convert(left, right):
if left > right:
return None
mid = (left + right) // 2
node = TreeNode(nums[mid])
node.left = convert(left, mid - 1)
node.right = convert(mid + 1, right)
return node
return convert(0, len(nums) - 1)
- Goでも書いてみます！
func sortedArrayToBST(nums []int) *TreeNode {
if len(nums) == 0 {
return nil
}
return &TreeNode{
Val: nums[len(nums)/2],
Left: sortedArrayToBST(nums[:len(nums)/2]),
Right: sortedArrayToBST(nums[len(nums)/2+1:]),
}
}
Author And Source
この問題について(LeetCodeに毎日挑戦してみた 108. Convert Sorted Array to Binary Search Tree（Python、Go)), 我々は、より多くの情報をここで見つけました https://qiita.com/ishishow/items/6227e3f1e255e8350111著者帰属：元の著者の情報は、元のURLに含まれています。著作権は原作者に属する。
Content is automatically searched and collected through network algorithms . If there is a violation . Please contact us . We will adjust (correct author information ,or delete content ) as soon as possible .