leetcode 刷题108109

# Definition for a  binary tree node
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None

class Solution: def sortedArrayToBST(self, num): if not num: return None mid = len(num) // 2 root = TreeNode(num[mid]) root.left = self.sortedArrayToBST(num[:mid]) root.right = self.sortedArrayToBST(num[mid+1:]) return root

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
 

# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None

# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None

class Solution: def sortedListToBST(self,head): cnt = 0 copy = head while head is not None: cnt+=1 head = head.next return self.constructBST_fromList(copy,cnt)[0] def constructBST_fromList(self,begin,length): if length==0: return None,begin mid = length//2 left,cur = self.constructBST_fromList(begin,mid) node = TreeNode(cur.val) node.left = left right,cur = self.constructBST_fromList(cur.next,length-mid-1) node.right = right return node,cur

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
 

class Solution(object): def sortedListToBST(self, head): if not head: return if not head.next: return TreeNode(head.val) fast = head slow = None while fast and fast.next: fast = fast.next.next slow = head if slow is None else slow.next node = TreeNode(slow.next.val) tmp = slow.next.next slow.next = None node.left = self.sortedListToBST(head) node.right = self.sortedListToBST(tmp) return node

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
 

文章来源: maoli.blog.csdn.net，作者：刘润森！，版权归原作者所有，如需转载，请联系作者。

原文链接：maoli.blog.csdn.net/article/details/90723458