Tree order traversal Problem (In-odrer Basic)
Tree order traversal Problem (In-odrer Basic) — #LeetCode #Tree순회 #Treeorder #inrode #traversal #treetraversal #treeinorder #개발자의도구들 on...
#LeetCode #Tree순회 #Treeorder #inrode #traversal #treetraversal #treeinorder #개발자의도구들
- only 파이썬
- 목표 참고 : 여기
Tree
Graph이론은 CS의 한 획을 긋는 중요한 이론이다. 특히나 여러가지 개념들이 나오는데 이들을 따로 정리해두지 않으면 까먹는 경우가 많다.
- 대부분 영어로 되어있기 때문에 의미지를 파악해서 외워두면 매우 직관적이라 기억하기 쉽다.
Tree의 경우 기본적으로 나무를 뜻하는데 나무는 잎사이가 서로 연결되지 않는 형태이다. 그래서 가족 계보같은 것들도 Tree라고 부른다.
Graph에서는 Tree를 흔히 cycle이 없는 Graph라고 부른다. 보통은 binary Tree를 많이 기억하지만, B Tree같이 Binary가 아닌 형태도 많다.
Tree order Traversal Problemns
Tree문제 중에서도 Tree order 문제는 매우 유명하다. 정보처리기사, 학교 시험 등 CS 관련 시험에서 단골로 등장하는 문제이다.
근데 이게 역시나 영어로 용어를 정하다 보니 헷갈리는 경우가 많다. 이번 기회에 정리하고자 한다.
🔑💡key point!
1. in-, pre-, post- 는 모두 root의 위치를 나타낸다.
2. 탐색 순서는 무조건 좌 -> 우 순이다.
위의 핵심 포인트만 기억하면 어려울게 없다.
in-order의 경우 좌 -> root > 우 형태이다. 좌와 우 사이에 root가 들어가 in-이라는 접두사가 붙었다.
💡✅ 영어단어는 항상 physical한 속성을 먼저 봐야한다.
pre-order: root -> 좌 -> 우
post-order: 좌-> 우 -> root
구현 연습
LeetCode(esay 94. Binary Tree Inorder Traversal) 77.9%
아주 단순한 문제이다 그냥 in-order을 구현해주면 된다.
✅ recursive로 탐색하기
✅ DFS로 탐색하기
크게 두 가지 방법이 사용되는데 쉬운 문제이기 때문에 둘 다 다뤄 보도록 하자.
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def inorderTraversal(self, root):
results = []
"""
:type root: Optional[TreeNode]
:rtype: List[int]
"""
if root == None:
return []
results.append(self.inorderTraversal(root.left))
results.append(root.val) #
results.append(self.inorderTraversal(root.right))
refactor = []
ref_type = type(refactor)
for result in results:
if result == None:
continue
if type(result) == type([1]):
for res in result:
if res == None:
continue
refactor.append(res)
continue
refactor.append(result)
return refactor
- 재귀로 하는 방법
- 구현이 간단한데, return 처리에서 좀 애를 많이 먹었다...
- 좀 더 깔금하게 작성할 수 는 없을까?
class Solution(object):
def inorderTraversal(self, root):
"""
:type root: Optional[TreeNode]
:rtype: List[int]
"""
result = []
def Traverse(current_node):
# Base case: if null
if current_node is None:
return
# Recur on the left subtree
Traverse(current_node.left)
# Append the current node
result.append(current_node.val)
# Recur on the right subtree
Traverse(current_node.right)
if root is not None:
Traverse(root)
return result
- 나도 처음 보는 형태인데 이런식으로 def 내부에 def를 사용하여 새로운 method를 사용할 수 있다.
DFS로 구현하기
모르겠음 ..
한번도 구현을 안해봐서 어덯게 하는지 모르겠다..
- 몇일 고민해보고 모르면 답을 보자.