트리 문제 풀다보면 자주 보는 용어들인데도 볼 때마다 새롭고 헷갈려서...
이건 아무래도.. 한 번 정리해야 할 것 같다...
1. Preorder Traversal
한국어로는 전위순회라고 하며 node가 주어질 때,
node를 방문 → left 방문 → right 방문
위의 순서대로 순회한다.
위와 같은 트리를 Preorder Traversal 한다면,
1 → 2 → 4 → 8 → 9 → 5 → 3 → 6 → 7 순으로 방문하게 된다.
리트코드: https://leetcode.com/problems/binary-tree-preorder-traversal/
1. Inorder Traversal
한국어로는 중위순회라고 하며,
left를 방문 → node 방문 → right 방문
위의 순서대로 순회한다.
위와 같은 트리를 Inorder Traversal 한다면,
8 → 4 → 9 → 2 → 5 → 1 → 3 → 6 → 7 순으로 방문하게 된다.
리트코드: https://leetcode.com/problems/binary-tree-inorder-traversal/
1. Postorder Traversal
한국어로는 후위순회라고 하며,
모든 left를 방문 → 모든right를 방문→ node 방문
위의 순서대로 순회한다.
모든 left 및 right를 방문한다 할 때, 가장 deep한 노드부터 방문한다는 것을 기억해야 한다.
위와 같은 트리를 Postorder Traversal 한다면,
4 → 7 → 8 → 5 → 2 → 9 → 6 → 3 순으로 방문하게 된다.
리트코드: https://leetcode.com/problems/binary-tree-postorder-traversal/
1. Levelorder Traversal
node가 주어질 때, BFS 식으로 방문한다고 생각하면 편하다.
자신을 방문 후, 다음 depth의 노드들을 왼쪽부터 순서대로 방문한다.
위와 같은 트리를 Levelorder Traversal 한다면,
1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 9 순으로 방문하게 된다.
리트코드: https://leetcode.com/problems/binary-tree-level-order-traversal/