LeetCode 94(Binary Tree In-order Traversal, java)

0. 문제

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

Binary Tree Inorder Traversal - LeetCode

 

1. 문제 설명

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

- 주어진 이진트리를 중위 순회 순서로 탐색하여, 방문한 노드의 값을 배열에 담아 반환하는 것이 문제의 핵심이다. 

 

2. 문제 해설

a) 첫 번째 접근

- 우선 중위 순회는 좌측 자식 노드 - 부모 노드 - 우측 자식 노드 순서로 탐색한다.

- 이 순서를 그대로 재귀 함수로 작성하면 끝이다. 

 

b) 두 번째 접근

- 더 이상 좌측 자식이 존재하지 않는 경우, 이전 노드로 돌아간다.

- 여기서 설명과 이해가 쉽도록, 위에서 언급한 "이전 노드"를 노드 A라고 명시하겠다.

 

- 노드 A는 어떤 부모 노드의 좌측 노드 또는 어떤 부모 노드일 수 있다.

- 어떤 부모 노드가 좌측 자식 노드(= A)를 가지는 경우, 노드 A는 어떤 부모 노드의 좌측 노드다.

- 어떤 부모 노드가 좌측 자식 노드를 가지지 않는 경우, 노드 A는 "어떤 부모 노드"가 된다. 

 

- 즉, 왼쪽 노드부터 계속 탐색하여 더 이상 왼쪽 노드가 존재하지 않는 시점(= null)에 이전 노드(= 상위 노드)로 돌아간다.

- 그리고 해당 노드의 값을 배열에 저장한다. 

- 이후 오른쪽 노드의 탐색을 시작한다. 

 

- 이 과정을 그대로 재귀 함수로 구현하면 된다.  

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

 

3. 정답 코드

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