[おかず鶏と一緒に問題を書く(python)]LeetCode 108.秩序配列を二叉探索ツリーに変換する(Convert Sorted Array to Binary Search Tree)
1206 ワード
原題
昇順に配列された秩序配列を、高さバランスツリーに変換します.
本題では,1つの高さバランスツリーとは,1つのツリーの各ノードの左右2つのサブツリーの高さ差の絶対値が1を超えないことを指す.
例:
与えられた秩序配列:[−10,−3,0,5,9]であり、可能な答えは、[0,−3,9,−10,null,5]であり、以下のような高平衡二叉探索ツリーを表すことができる.
構想
二叉探索ツリー(Binary Search Tree)は、左のサブツリーが空でない場合、左のサブツリー上のすべてのノードの値がそのルートノードの値よりも小さい性質を有する二叉ツリーである.右サブツリーが空でない場合、右サブツリーのすべてのノードの値はルートノードの値よりも大きくなります.テーマは秩序配列を与え,高さバランスを満たすために配列の中間位置を選択して配列を分割し,この点はルートノードであり,分割された左半分は左サブツリーを構成し,右半分は右サブツリーを構成する.その後、再帰を利用して木全体を構成する.
コード#コード#
昇順に配列された秩序配列を、高さバランスツリーに変換します.
本題では,1つの高さバランスツリーとは,1つのツリーの各ノードの左右2つのサブツリーの高さ差の絶対値が1を超えないことを指す.
例:
与えられた秩序配列:[−10,−3,0,5,9]であり、可能な答えは、[0,−3,9,−10,null,5]であり、以下のような高平衡二叉探索ツリーを表すことができる.
0
/ \
-3 9
/ /
-10 5
構想
二叉探索ツリー(Binary Search Tree)は、左のサブツリーが空でない場合、左のサブツリー上のすべてのノードの値がそのルートノードの値よりも小さい性質を有する二叉ツリーである.右サブツリーが空でない場合、右サブツリーのすべてのノードの値はルートノードの値よりも大きくなります.テーマは秩序配列を与え,高さバランスを満たすために配列の中間位置を選択して配列を分割し,この点はルートノードであり,分割された左半分は左サブツリーを構成し,右半分は右サブツリーを構成する.その後、再帰を利用して木全体を構成する.
コード#コード#
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def sortedArrayToBST(self, nums):
"""
:type nums: List[int]
:rtype: TreeNode
"""
if len(nums) == 0:
return None
mid = len(nums) // 2
root = TreeNode(nums[mid])
root.left = self.sortedArrayToBST(nums[:mid])
root.right = self.sortedArrayToBST(nums[mid+1:])
return root