108. Convert Sorted Array to Binary Search Tree
https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/
solution
class Solution:
def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
if not nums:
return None
mid = len(nums) // 2
root = TreeNode(val=nums[mid])
root.left = self.sortedArrayToBST(nums[:mid])
root.right = self.sortedArrayToBST(nums[mid+1:])
return root
时间复杂度:O() 空间复杂度:O()
follow up
*426. Convert Binary Search Tree to Sorted Doubly Linked List
# 中序,记录前一个pre, 以及根节点first
class Solution:
def __init__(self):
self.first = None
self.pre = None
def treeToDoublyList(self, root):
self.dfs(root)
self.first.left = self.pre # 循环链表, dfs后最后一位正是self.pre
self.pre.right = self.first
return self.first
def dfs(self, root):
if not root:
return
self.dfs(root.left)
if not self.first: # 记录首位
self.first = root
if self.pre: # 遍历过程中,一直记录前一位. 每一轮进行指针更新
root.left = self.pre
self.pre.right = root
self.pre = root
self.dfs(root.right)
时间复杂度:O(n) 空间复杂度:O(log(n))
Last updated