Algorithm | [LeetCode 94] Binary Tree Inorder Traversal

문제

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

 

입력

root = [1,null,2,3]

 

출력

[1,3,2]

 

제한

• The number of nodes in the tree is in the range [0, 100].
• -100 <= Node.val <= 100

 

 

풀이1 (js)

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function inorderTraversal(root: TreeNode | null): number[] {
    if (!root) return [];
    const result = [];

    function dfs(node: TreeNode | null) {
        if (node) {
            if (node.left) dfs(node.left);
            if (node.val !== null) result.push(node.val);
            if (node.right) dfs(node.right);   
        }
    }
    dfs(root);
    return result;
};

 

풀이2 (Java)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private Queue q = new LinkedList();
    private List<Integer> result = new ArrayList();
    
    private void dfs(TreeNode node) {
        if (node != null) {
            dfs(node.left);
            result.add(node.val);
            dfs(node.right);
            return;
        }
        return;
    }

    public List<Integer> inorderTraversal(TreeNode root) {
        if (root == null) return result;
        dfs(root);
        return result;
    }
}

 

두 풀이 모두 언어만 다를 뿐, 본질적으로는 동일한 방식이다. 깊이 우선 탐색(DFS, Depth-First Search)을 활용한 풀이이며, DFS는 재귀나 스택을 이용해 구현할 수 있다. 이 중 재귀 방식은 코드가 더 명확하게 드러나 구현이 훨씬 쉽다.

 

Inorder traversal 은 이진 트리에서 왼쪽 → 루트 → 오른쪽 순서로 노드를 방문하는 방식이다. DFS로 구현할 때도, 먼저 왼쪽 자식 노드를 따라 트리의 끝까지 내려가며 재귀 호출을 진행한다. 그런 다음 현재 노드의 값을 결과 배열에 추가하고, 마지막으로 오른쪽 자식 노드를 탐색하는 방식으로 구현된다.