You have an integer list (unique values), what you need to do is build a tree met following conditions:
Binary tree
Each node value small than its children’ value
In-order traverse sequence same as the array list sequence
intput: [5, 3, 7, 4, 1, 2 ,6]
output
____1
__3___2
5___4____6
______7
My Solution:
class Node:
def __init__(self,val):
self.val=val
self.child1=None
self.child2=None
self.parent=None
def construct(input):
if input==[]:
return None
root=Node(input[0])
prev=root
for i in range(1,len(input)):
if input[i]<root.val:
temp=Node(input[i])
temp.child1=root
root.parent=temp
prev=temp
root=temp
else:
if prev.val>input[i]:
temp=Node(input[i])
temp_p=prev.parent
temp.child1=prev
temp.parent=temp_p
temp_p.child2=temp
prev.parent=temp
prev=temp
elif prev.child2==None:
temp=Node(input[i])
temp.parent=prev
prev.child2=temp
prev=temp
return root
def inorder(root):
if root==None:
return None
inorder(root.child1)
print(root.val)
inorder(root.child2)
return
inorder(construct([1,2,3,4,5,6,7])) Comments (6)
