트리 순회 (전위, 후위, 중위)

트리순회

• 전위:
  전위 순회는 우선순위가 적혀 져있는대로 top -> left -> right 이다. 매 노드에서 left를 먼저간 후 right를 간다.
  스택을 이용한 반복문으로 쉽게 구현할 수 있다. 시간 복잡도는 O(N).
• 후위:
  후위 순회는 우선순위가 left -> right -> top이다. 왼쪽 노드가 빌때까지 쭉 왼쪽을 따라 내려간 뒤 왼쪽 -> 오른쪽 -> 부모 를 반복하며 탐색한다.
  재귀호출을 이용해 구현하면 반복문보다 가독성이 좋다. 시간복잡도는 O(N)이다.
• 중위:
  중위 순회는 우선순위가 left -> top -> right 이다. 윈쪽노드가 빌때까지 쭉 내려간 뒤 왼쪽 -> 부모 -> 오른쪽을 반복하며 탐색한다.
  나는 stack 과 while문을 이용해 구현하는 게 더 편했다. 시간복잡도는 마찬가지로 O(N)이다.