[JAVA] LeetCode 94 - Binary Tree Inorder Traversal

 

문제

Given the root of a binary tree, return the inorder traversal of its nodes' values.
이진 트리의 루트가 주어지면, 중위 순회(inorder traversal)하여 노드의 값을 출력하라.

 

풀이 방법

트리를 순회 하는 방법에는 대표적으로 3가지 방법이 있는데

각각 전위(preorder), 중위(inorder), 후위 순회(postorder)이다.

 

 

전위의 경우, ROOT를 가장 먼저 탐색하는 방법으로

ROOT -> LEFT 자식 노드 -> RIGHT 자식 노드 순으로 탐색하며,

 

 

후위의 경우, ROOT를 가장 나중에 탐색하는 방법으로

LEFT 자식 노드 -> RIGHT 자식 노드 -> ROOT 순으로 탐색한다.

 

 

오늘 문제에 주어진 중위 순회의 경우, LEFT 자식 노드 -> ROOT -> RIGHT 자식 노드 순으로 탐색하는 방법이다.

 

 

문제 풀이는 단순하다.

 

위에 언급한 중위 순회를 고려하여 LEFT -> ROOT -> RIGHT 순으로 탐색하게끔 재귀 함수를 구현했다.

번거롭지만 재귀 함수는 그림을 그려가면서 차근 차근 따라가면 이해하기가 쉽다.

 

 

코드

class Solution {
    List<Integer> list;
    
    public List<Integer> inorderTraversal(TreeNode root) {
        list = new ArrayList<Integer>();
        inorder(root);
        return list;
    }
    
    public void inorder(TreeNode node) {
        if(node != null) {
            if(node.left != null) inorder(node.left);
            list.add(node.val);
            if(node.right != null) inorder(node.right);
        }  
    }
}