[HackerRank] Tree: Preorder Traversal

Problem

---

Complete the preOrder function in the editor below, which has 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's preorder traversal as a single line of space-separated values.

Input Format

Our test code passes the root node of a binary tree to the preOrder function.

Constraints

1 ≤ Nodes in the tree ≤ 500

Output Format

Print the tree's preorder traversal as a single line of space-separated values.

Sample Input

     1
      \
       2
        \
         5
        /  \
       3    6
        \
         4

Sample Output

1 2 5 3 4 6

Explanation

The preorder traversal of the binary tree is printed.

---

preOrder 함수를 완성하세요. 이 함수는 이진 트리의 루트 노드를 가리키는 포인터 하나를 매개변수로 받습니다. 이 함수는 트리의 전위 순회 결과를 한 줄로 출력해야 합니다. 각 노드의 값을 공백으로 구분하여 출력하세요.

 

입력 형식

테스트 코드가 이진 트리의 루트 노드를 preOrder 함수에 전달합니다.

 

제약 사항

• 트리의 노드 개수는 1 이상 500 이하입니다.

출력 형식

트리의 전위 순회 결과를 공백으로 구분하여 한 줄로 출력합니다.

 

 

728x90

 

 

Solution

---

/* you only have to complete the function given below.  
Node is defined as  

class Node {
    int data;
    Node left;
    Node right;
}

*/

public static void preOrder(Node root) {
    if (root == null) {
        return;
    }
    System.out.print(root.data + " ");
    preOrder(root.left);
    preOrder(root.right);
}

 

이 코드는 전위 순회를 수행하여, 현재 노드 -> 왼쪽 자식 -> 오른쪽 자식 순으로 탐색합니다.

---

위 preOrder 함수는 이진 트리를 전위 순회 방식으로 탐색하는 재귀적인 접근 방식을 사용하여 구현되었습니다. 전위 순회(pre-order traversal)는 현재 노드를 먼저 방문한 후, 왼쪽 자식 노드와 오른쪽 자식 노드를 순서대로 방문하는 탐색 방법입니다.

public static void preOrder(Node root) {
    if (root == null) {
        return;
    }
    System.out.print(root.data + " ");
    preOrder(root.left);
    preOrder(root.right);
}

 

 

1. 종료 조건: if (root == null) { return; }
   • 이 부분은 재귀 호출의 종료 조건으로, 현재 노드 root가 null이면 함수가 아무 작업도 하지 않고 종료됩니다.
   • 트리의 잎 노드(leaf node)에 도달한 경우, 그 아래에는 자식 노드가 없으므로 root가 null일 때 바로 리턴하여 재귀 호출을 멈춥니다.
2. 현재 노드 방문: System.out.print(root.data + " ");
   • 전위 순회 방식에 따라, 먼저 현재 노드의 data 값을 출력합니다.
   • 이 출력은 공백으로 구분되며, 하나의 줄에 모든 노드 값을 출력하게 됩니다.
3. 왼쪽 자식 노드 방문: preOrder(root.left);
   • 현재 노드의 왼쪽 자식 노드를 재귀적으로 호출하여 방문합니다.
   • 전위 순회에서는 항상 왼쪽 자식 노드를 먼저 탐색하므로, 이 호출이 오른쪽 자식 노드 호출보다 앞에 위치합니다.
4. 오른쪽 자식 노드 방문: preOrder(root.right);
   • 왼쪽 자식 노드를 다 방문한 후, 현재 노드의 오른쪽 자식 노드를 재귀적으로 호출하여 방문합니다.
   • 이로써 전위 순회의 "현재 노드 -> 왼쪽 -> 오른쪽" 순서가 완성됩니다.

트리가 다음과 같을 때,

     1
      \
       2
        \
         5
        /  \
       3    6
        \
         4

전위 순회 과정은 다음 순서로 진행됩니다:

1. 노드 1 방문 → 출력: 1
2. 노드 2 방문 → 출력: 1 2
3. 노드 5 방문 → 출력: 1 2 5
4. 노드 3 방문 → 출력: 1 2 5 3
5. 노드 4 방문 → 출력: 1 2 5 3 4
6. 노드 6 방문 → 출력: 1 2 5 3 4 6

최종 출력 결과는 1 2 5 3 4 6이 됩니다.

 

시간 및 공간 복잡도

• 시간 복잡도: O(n), 여기서 n은 트리의 노드 개수입니다. 각 노드를 한 번씩 방문하기 때문입니다.
• 공간 복잡도: O(h), 여기서 h는 트리의 높이입니다. 재귀 호출을 사용할 때 호출 스택의 최대 깊이는 트리의 높이에 비례합니다.