항해99 - 3주차, 이진 트리 직렬화 & 역직렬화
Today I learned
2022/01/26
회고록
1/26
항해 99, 알고리즘 2주차
교재 : 파이썬 알고리즘 인터뷰
이진트리
1. 이론
이진 트리(binary tree)의 정의
트리 중에서 가장 많이 쓰이는 트리가 이진트리이다. 모든 노드가 2개의 서브 트리를 가지고 있는 트리를 이진 트리(binary tree) 라고 한다. 서브트리는 공집합일 수 있다. 따라서 이진트리의 노드에는 최대 2개까지의 자식 노드가 존재할 수 있고 모든 노드의 차수가 2 이하가 된다. (차수(degree)는 어떤 노드가 가지고 있는 자식 노드의 개수)
이진트리
공집합이거나
루트와 왼쪽 서브 트리, 오른쪽 서브 트리로 구성된 노드들의 유한 집합으로 정의된다. 이진트리의 서브트리들은 모두 이진트리여야 한다.
이진트리의 성질
n개의 노드를 가진 이진트리는 정확하게 n-1개의 간선을 가진다. 그 이유는 이진트리에서의 노드는 루트를 제외하면 정확하게 하나의 부모노드를 가진다. 그리고 부모와 자식 간에는 정확하게 하나의 간선만이 존재한다.
높이가 h인 이진트리의 경우, 최소 h개의 노드를 가지며 최대 2의h제곱 -1개의 노드를 가진다.
2. 문제
Given the root of a binary tree, invert the tree, and return its root.
Example 1:
Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]
https://leetcode.com/problems/invert-binary-tree/
3. MySol
- BinaryTree, BFS
#binary DFS Templates
from collections import deque
from binary.prac import make_tree_by
from binary.structures import TreeNode
def solution(binaryTreeList):
root = make_tree_by(binaryTreeList, 0)
queue = deque([root])
result = []
def serialize(queue):
while queue:
node = queue.popleft()
if node:
#
#로직 구현
#
result.append(str(node.val))
queue.append(node.left)
queue.append(node.right)
else:
result.append('#')
return result
result=serialize(queue)
print(f'{result}')
def deserialize(serializedStr):
nodes = serializedStr
root = TreeNode(int(nodes[0]))
queue = deque([root])
index = 1
while queue:
node=queue.popleft()
if nodes[index] is not '#':
#left될 놈
node.left = TreeNode(nodes[index])
queue.append(node.left)
index+=1
if nodes[index] is not '#':
#right될 놈
node.right = TreeNode(nodes[index])
queue.append(node.right)
index+=1
return root
root2=deserialize(result)
return root
if __name__ == '__main__':
binTree = [1,2,3,None,None,4,5]
result = solution(binTree)
print('result : ' + str(result))
4. 배운 점
- 이진트리에 대한 이해
- BFS를 이용, 조건로직 구현
5. 총평
이진트리, BFS 훈련
Author And Source
이 문제에 관하여(항해99 - 3주차, 이진 트리 직렬화 & 역직렬화), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jsw4215/항해99-3주차-이진-트리-직렬화-역직렬화저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)