문제 정의

• input: Tree 자료 구조의 root
• output: 중위 순회로 돌았을 때의 방문하는 노드를 순서대로 담은 배열

2025.02.03

레슨

자료구조를 알아야 하는 이유

• 새로운 자료구조는 언제, 왜 생기는건가? 실제로 다른 모양새인가? 리트코드에서 보면 linkedlist든 tree든 배열이든 대괄호에 똑같이 들어있는 모양이다.
  • 표현 방식상 비슷하게 보이는 것일 뿐, 정작 속은 너무 달랐다.
• 자료구조를 보면 개발자가 어떤 사고로 데이터를 다루고자 하는지, 무엇을 중요하게 생각하는지 드러날 것.
  • 왜 배열로 관리하는지, 객체로 관리하는지 까지. 개발은 변수를 다루는 것이 중요한데, 자료구조는 변수를 담는 그릇이기 때문에 중요할 것.
• 흔한 자료구조 먼저 보면 배열, 객체. 이 둘을 우리는 각각 사용하기를 선호하고 필요성을 특히 더 느끼는 순간이 있음. 그렇다고 배열을 쓰면 좋은 상황에서 절대 객체를 사용하면 안되는 것도 아님. 쓰기 좋을 때가 있는 것.

왜 하필 이진트리를 줬을까. 혹시 힌트?

• 이진트리는 각 노드가 Max 2개의 자식을 갖는게 대표 특징임 ⇒ “순회 방향”이 명확함.
• left, right 방향도 고정이라 3개, 4개… 등 늘어나면 이건 구조가 굉장히 복잡해진다.
• 따라서 자식 노드 → 부모 노드로 방문하는 패턴을 학습할 수 있게 문제가 짜여진듯.

트리 순회, 그 중 ‘중위 순회’