LeetCode 109 번 문제 - 질서 있 는 링크 를 이 진 검색 트 리 로 변환 - Python 구현

title: LeetCode No.109
categories:

OJ

LeetCode

tags:

Programing

LeetCode

OJ

LeetCode 109 번 문제 - 질서 있 는 링크 를 이 진 트 리 로 변환 합 니 다.
자신의 코드 오픈 소스 창고: click here 환영 Star 와 Fork
제목 설명
단일 체인 표를 지정 합 니 다. 그 중의 요 소 는 오름차 순 으로 정렬 하여 고도 의 균형 을 가 진 이 진 검색 트 리 로 변환 합 니 다.
이 문제 에서 하나의 높이 균형 이 진 트 리 는 이 진 트 리 의 각 노드 의 좌우 두 개의 나무의 높이 차 이 를 말 하 는 절대 치 는 1 을 초과 하지 않 는 다.

  :

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

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

      0
     / \
   -3   9
   /   /
 -10  5

코드

# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
# Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution(object):
    res = []
    def balancedBST(self,partNode):
        """
                           ，                
                ：                        
        """
        if len(partNode) == 1:
            return TreeNode(partNode[0])
        middle = int(len(partNode)/2)
        node = TreeNode(partNode[middle])
        node.left = self.balancedBST(partNode[0:middle])
        if middle == len(partNode)-1:
            node.right = None
        else:
            node.right = self.balancedBST(partNode[middle+1:])
        return node
    def nodeList2SortedList(self,node):
        """
                    
        """
        if node != None:
            self.res.append(node.val)
            self.nodeList2SortedList(node.next)

    def sortedListToBST(self, head):
        """
        :type head: ListNode
        :rtype: TreeNode
            ：
                    ：                   1
                       ，          

                  ，                           
                 108    ，             

                            ，          ，         
        """
        self.nodeList2SortedList(head)
        return self.balancedBST(self.res)