LeetCode 144(Binary Tree Preorder Traversal, java)

0. 문제

https://leetcode.com/problems/binary-tree-preorder-traversal/

Binary Tree Preorder Traversal - LeetCode

 

1. 문제 설명

- 문제에서 이진트리(root)가 주어진다.

- 이 문제는 이진트리를 전위 순회(Preorder)로 탐색하여 방문한 노드를 리스트로 반환하는 것이 핵심이다. 

 

- 이진 트리를 탐색하는 방법에는 3가지가 있다.

  → 전위 순회(Pre-order), 중위 순회(In-order), 후위 순회(Post-order)

 

- 명칭 자체가 어렵다 보니까, 탐색 순서를 암기하기가 쉽지 않다. 

- 한가지 팁을 주자면 부모를 탐색하는 순서를 고려하여 이를 외우면 쉽게 암기할 수 있다.

 

  → 전위 순회 - 부모 노드를 가장 먼저(= 전, Pre) 탐색한다. 

  → 중위 순회 - 부모 노드를 중간 순번(= 중, In)으로 탐색한다.

  → 후위 순회 - 부모 노드를 가장 마지막(= 후, Post)으로 탐색한다.  

 

2. 문제 해설

a) 첫 번째 접근

- 우선 전위 순회(Preorder)를 알아야 한다.

- 전위 순회는 부모 - 좌측 자식 노드 - 우측 자식 노드 순으로 방문하는 것을 의미한다.

 

- 전체적으로 봤을 때, 부모 노드를 기준으로 좌측 자식 노드를 우선적으로 탐색한다. 

- 단말 노드를 만날 때까지 좌측 자식 노드를 탐색한 후, 해당 단말 노드의 부모 노드로 돌아가서 우측 자식 노드를 탐색한다.

    → 다시 부모 노드로 다시 돌아간다는 부분에서 재귀함수를 사용하는 이유가 발현된다. 

 

- 우측 자식 노드를 탐색할 때에도 좌측 자식 노드를 가진다면, 이를 우선적으로 탐색한다. 

 

- 이 과정을 재귀 함수로 표현하면 끝이다.

- 다음 코드를 보면서 이해해보자. 

 

3. 정답 코드

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        
        List<Integer> visited = new ArrayList<>();
        traversal(root, visited);
        
        return visited;
    }
    
    public void traversal(TreeNode root, List<Integer> visited) {
        
        if(root == null) return;
        
        visited.add(root.val);
        traversal(root.left, visited);
        traversal(root.right, visited);
    }
}