1 | 오늘의 문제

1. Binary Tree Inorder Traversal

Given the root of a binary tree, return the inorder traversal of its nodes' values.

오늘의 문제는 간단하다. 이진트리에서 중위순회하는 solution을 만들면 된다.

2. 중위순회(Inorder Traversal)

정보처리기사 시험 준비가 이렇게 도움될 줄 몰랐다. 덕분에 이게 뭐였더라하는 복습 시간 가지고 코드에만 집중할 수 있었다.

1. 전위순회 preorder traversal
   뿌리 -> 왼쪽 자식 노드 -> 오른쪽 자식 노드
2. 중위순회 inorder traversal
   왼쪽 자식 노드 -> 뿌리 -> 오른쪽 자식
3. 후위순회 postorder traversal
   왼쪽 자식 -> 오른쪽 자식 -> 뿌리

3. 풀이

지난번 풀었던 이진탐색트리(BST)에서 재귀 용법에 대해서 활용했기에, 같은 방식을 활용하자 생각하였다.

import java.util.*;

class Solution {
    List<Integer> result = new ArrayList<>();

    public List<Integer> inorderTraversal(TreeNode root) {
        if (root != null) {
            inorderTraversal(root.left);
            result.add(root.val);

            inorderTraversal(root.right);
        }
        return result;
    }
}

계속 사용하는 list인 result를 Class에서 선언해 재귀함수를 거치는 동안 전역으로 사용할 수 있게 했다. 다른 방법으로 선언하는 방법은 아래에 있다.

4. 다른 풀이

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        helper(root, res);
        return res;
    }

    public void helper(TreeNode root, List<Integer> res) {
        if (root != null) {
            helper(root.left, res);
            res.add(root.val);
            helper(root.right, res);
        }
    }
}

함수를 활용해 list를 같이 선언하는 방법이 있다.