LeetCode-Python-108. 秩序配列を二叉検索ツリーに変換するには

昇順に配列された秩序配列を、高さバランスツリーに変換します.
本題では,1つの高さバランスツリーとは,1つのツリーの各ノードの左右2つのサブツリーの高さ差の絶対値が1を超えないことを指す.
例:

      : [-10,-3,0,5,9],

        ：[0,-3,9,-10,null,5]，                  ：

      0
     / \
   -3   9
   /   /
 -10  5

 
考え方:
入力配列は既存のシーケンスであり,BSTの中シーケンスが遍歴することに相当するので,中シーケンスが遍歴する逆プロセスに従えばBSTを確立できる.
中順遍歴配列の中間要素nums[mid]はrootであり、
左サブツリーはnums[:mid]で確立されたBST,右サブツリーはnums[mid+1:]で確立されたBSTである.

# 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 not nums:
            return None
             
        def dfs(start, end):
            if end < start:
                return 
            
            mid = (end + start) // 2
            root = TreeNode(nums[mid])
            
            root.left = dfs(start, mid - 1)
            root.right = dfs(mid + 1, end)
            
            return root

        return dfs(0, len(nums) - 1)

次は2019.6.25に書きます.

class Solution(object):
    def sortedArrayToBST(self, nums):
        """
        :type nums: List[int]
        :rtype: TreeNode
        """
        if not nums:
            return None
        l = len(nums)
        root = TreeNode(nums[l // 2])
        root.left = self.sortedArrayToBST(nums[:l//2])
        root.right = self.sortedArrayToBST(nums[l//2 + 1:])
        return root