108. Convert Sorted Array to Binary Search Tree Leetcode Python
Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
まずBST left構造bstは最後にnodeを返す.
we can divide the array into 3 parts, one for root. one for the left subtree one for the right subtree. then recursively build the tree.
Iterative method to do this problem is a little more complex. we need extra data structure to store the low, high and node information
code is as follow
まずBST left
we can divide the array into 3 parts, one for root. one for the left subtree one for the right subtree. then recursively build the tree.
# Definition for a binary tree node
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# @param num, a list of integers
# @return a tree node
def makeTree(self,num,start,end):
if start>end:
return None
mid=start+(end-start)/2
node=TreeNode(num[mid])
node.left=self.makeTree(num,start,mid-1)
node.right=self.makeTree(num,mid+1,end)
return node
def sortedArrayToBST(self, num):
if len(num)==0:
return None
return self.makeTree(num,0,len(num)-1)Iterative method to do this problem is a little more complex. we need extra data structure to store the low, high and node information
code is as follow
# Definition for a binary tree node
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Marker:
def __init__(self, low, high, treenode):
self.low = low
self.high = high
self.treenode =treenode
class Solution:
# @param num, a list of integers
# @return a tree node
def sortedArrayToBST(self, num):
if len(num) == 0:
return None
if len(num) == 1:
return TreeNode(num[0])
stack = []
root = TreeNode(num[(len(num) - 1) / 2])
marker = Marker(0, len(num) - 1, root)
stack.append(marker)
while stack:
cur = stack.pop()
mid = (cur.low + cur.high) / 2
# low -> mid - 1
if mid - 1 >= cur.low:
leftnode = TreeNode(num[(mid - 1 + cur.low) / 2])
cur.treenode.left = leftnode
leftmarker = Marker(cur.low, mid -1, leftnode)
stack.append(leftmarker)
#mid + 1 -> high
if mid + 1 <= cur.high:
rightnode = TreeNode(num[(mid + 1 + cur.high) / 2])
cur.treenode.right = rightnode
rightmarker = Marker(mid + 1, cur.high, rightnode)
stack.append(rightmarker)
return root