Leetcode 뿌시기 - Tree 문제

<Week 7>

• Binary Tree Right Side View
• Symmetric Tree
• Recover Binary Search Tree
• Top K Frequent Elements

1. Binary Tree (이진 트리) : 보통 O(logn)의 time complexity (출처: https://starrykss.tistory.com/1911#:~:text=%EC%BB%B4%ED%93%A8%ED%84%B0%EB%8A%94%20%EB%8D%B0%EC%9D%B4%ED%84%B0%EB%A5%BC%200,%EC%9D%B4%ED%95%98%EB%A1%9C%20%EA%B5%AC%EC%84%B1%EB%90%98%EC%96%B4%20%EC%9E%88%EB%8B%A4.)

 

루트를 레벨 0으로 두면, 나뭇잎(leaf)들은 아래로 내려올 수록 레벨이 1씩 증가한다.

각 위치를 Node라고 하고, 각 노드는 edge로 연결되어 있다. 위 노드와 바로 아래 노드의 관계는 parent-child relationship이며, 자식 노드의 개수가 Degree이고, degree=0인 노드는 leaf라고 한다. 

트리의 차수는 차수가 가장 높은 노드를 기준으로 정한다.

Binary Tree는 모든 노드의 자식이 최대 2개인 트리이고, 최대 2개라는 표현은 0개, 1개, 2개일수 있음을 의미한다.

 

1) Binary Tree 클래스 정의 및 초기화 (출처: https://deok2kim.tistory.com/104)

이진 트리를 사용하기 위해 Node의 클래스를 정의해보자. Node 클래스는 노드값, 왼쪽 노드, 오른쪽 노드의 정보를 저장해야 한다. 초기 값으로는 왼쪽 노드와 오른쪽 노드는 비어두자.

class Node:
	def __init__(self, item):
    	self.val = item
        self.left = None
        self.right = None

Node 클래스를 만든 후 BinaryTree 클래스를 만들어 보자. 처음에는 Node 값이 없는, 노드 하나를 가진 트리로 초기화한다. 이제 여기에 노드를 추가/삭제/탐색할 수 있도록 메소드를 정의 해주어야 한다.

 

노드를 추가하는 메소드는 재귀를 이용해서 구현하면 된다. item 값을 추가했을 때 노드의 값이 None이라면 노드의 값을 item으로 한다. 노드의 값이 있다면 대소 비교를 통해 노드의 왼쪽으로 갈 것인지, 오른쪽으로 갈 것인지를 결정하며, 재귀적으로 끝에 도달하여 값을 추가하게 된다. 

class BinaryTree:
	def __init__(self):
    	self.head = None(None)
        self.preoder_list = []
        self.inorder_list = []
        self.postorder_list = []
    
    #head가 없을 경우
    def add(self, item):
    	if self.head.val is None:
        	self.head.val = item
        #head가 있으면 왼쪽 배치 or 오른쪽 배치
        else:
        	self.__add_node(self.head, item)
    #head가 있을 경우
    def __add_node(self, cur, item):
    	print('부모:', cur.val, '자식:', item)
        #head 값이 크면 왼쪽으로
        if cur.val >= item:
        	if cur.left is not None:
            	self.__add_node(cur.left, item)
           else:
               cur.left = Node(item)
        #head 값이 작으면 오른쪽으로
        else:
            if cur.right is not None:
        		self.__add_node(cur.right, item)
        	else:
           		cur.right = Node(item)

2) Binary Search Tree 탐색하기

def search(self, item):
	if self.head.val is None:
    	return False
    else:
    	return self.__search_node(self.head, item)
        
def __search_node(self, cur, item):
	print(cur.val, item)
    if cur.val == item:
    	return True
    else:
    	if cur.val >= item:
        	if cur.left is not None:
            	return self.__search_node(cur.left, item)
            else:
                return False
        else:
           if cur.right is not None:
               return self.__search_node(cur.right, item)
           else:
               return False

 

2. Binary Search Tree: 장점 탐색 속도 개선 & 단점 복잡함

이진 트리의 하나로, 노드에 대해 왼쪽 자식의 값이 노드의 값보다 작거나 같고, 오른쪽 자식의 값은 노드의 값보다 큰 경우를 의미. 

 

3.Binary Tree's Traversal (순회) - 노드 탐방! Stack or Recursin 사용

효과적으로 데이터를 검색하기 위해서 binary tree에서는 Preorder/ Inorder/ Postorder Traversal를 사용한다.

1) Preorder Traversal: 노드 -> 왼쪽 -> 오른쪽

2) Inorder Traversal: 왼쪽 -> 노드 -> 오른쪽

3) Postorder Traversal: 왼쪽 -> 오른쪽 -> 노드

class TreeNode():
	def __init__ (self):
    	self.left = None
        self.data = None
        self.right = None

	def preorder(node):
    	if node == None:
        	return
        print(node.data, end = '->')
        preorder(node.left)
        preorder(node.right)
    
    def inorder(node):
    	if node == None:
        	return
        inorder(node.left)
        print(node.data, end = '->')
        inorder(node.right)
    
    def postorder(node):
    	if node == None:
        	return
        postorder(node.left)
        postorder(node.right)
        print(node.data, end = '->')
   
   print('전위 순회 :', end = '')
   preorder(node1)
   print('끝')

   print('중위 순회 :', end = '')
   inorder(node1)
   print('끝')

   print('후위 순회 :', end = '')
   postorder(node1)
   print('끝')

Binary Search Tree example: 

https://starrykss.tistory.com/1911#:~:text=%EC%BB%B4%ED%93%A8%ED%84%B0%EB%8A%94%20%EB%8D%B0%EC%9D%B4%ED%84%B0%EB%A5%BC%200,%EC%9D%B4%ED%95%98%EB%A1%9C%20%EA%B5%AC%EC%84%B1%EB%90%98%EC%96%B4%20%EC%9E%88%EB%8B%A4.

[Python] 이진 트리(Binary Tree)

 

<Week 6>

• Path Sum
• Binary Tree Inorder Traversal
• Kth Largest Element in an Array
• Meeting Rooms II