트리 - 몸풀기 문제

### 문제 26 트리 순회

이진 트리를 표현한 리스트 nodes를 인자로 받음
이진 트리에 대하여 전위 순회, 중위 순회, 후위 순회 결과를 반환하는 함수 구현

시간 복잡도 : O(N)

# nodes는 배열, idx는 현재 노드의 인덱스
def preorder(nodes,idx):
	if idx<len(nodes):
    	ret=str(nodes[idx])+""
        ret+=preorder(nodes,idx*2+1)
        ret+=preoreder(nodes,idx*2+2)
        return ret
    else:
    	return ""
        #재귀함수는 스택처럼해서 만약 노드가 없으면 그 전 꺼로 복귀
def inorder(nodes,idx):
	if idx<len(nodes):
    	ret=inorder(nodes,idx*2+1)
        ret+=str(nodes[idx])
        ret+=inorder(nodes,idx*2+2)
        return ret
    else:
    	return ""
def postorder(nodes,idx):
	if idx<len(nodes):
    	ret=postorder(nodes,idx*2+1)
        ret+=postorder(nodes,idx*2+2)
        ret+=str(nodes[idx])
        return ret
 	else:
    	return ""
 def solution(nodes):
 	return[
    	preorder(nodes,0)[:-1] #[:-1]은 마지막 공백을 없앰
        inorder(nodes,0)[:-1]
        postorder(nodes,0)[:-1]
    ]
        

전위, 중위, 후위 연산 모두 각 노드를 한 번씩 방문하므로 시간 복잡도는 O(N)

### 문제 27 이진 탐색 트리 구현

첫번째 인수 lst를 이용하여 이진 탐색 트리를 생성하고 두번째 인수 search_lst에 있는 각 노드를 이진 탐색 트리에서 찾을 수 있는지 확인하여 True/False를 담은 리스트 result를 반환

시간 복잡도 : O(N^2)

class Node:
	def __init__(self,key):
    	self.left=None
        self.right=None
        self.val=key
class BST:
	def __init__(self):
    	self.root=None
    def insert(self,key):
		if not self.root:
        	self.root=Node(key)
        else:
        	curr=self.root
            while True:
            	if key<curr.val:
                	if curr.left:
                    	curr=curr.left
                    else:
                    	curr.left=Node(key)
                        break
                else:
                	if curr.right:
                    	curr=curr.right
                    else:
                    	curr.right=Node(key)
                        break
    def search(self,key):
    	curr=self.root
        while curr and curr.val!=key:
        	if key<curr.val:
            	curr=curr.left
            else:
            	curr=curr.right
    return curr
    
    def solution(lst,search_lst):
    	bst=BST()
        for key in lst:
        	bst.insert(key)
        result=[]
        
        for search_val in search_lst:
        	if bst.search(search_val):
            	result.append(True)
            else:
            	result.append(False)
    return result
                      

최악의 경우 이진 탐색 트리의 삽입 및 탐색 연산 시간 복잡도는 O(N)
이후 lst의 길이만큼 삽입하고 search_lst 길이만큼 탐색해야하므로
O(N*(N+M)), N이 M보다 훨씬 크므로 M은 무시 가능 -> O(N^2)