94. Binary Tree Inorder Traversal

이진 트리의 노드를 중위 순회(inorder traversal)하여 노드 값들을 리스트에 저장하는 문제입니다. 중위 순회는 트리를 다음과 같은 방식으로 순회합니다:

먼저, 왼쪽 하위 트리를 순회합니다.
현재 노드를 방문하고 처리합니다.
마지막으로, 오른쪽 하위 트리를 순회합니다.
즉, 이 문제에서는 이진 트리를 중위 순회하여 노드 값을 리스트에 저장해야 합니다.

문제 설명:

주어진 이진 트리의 루트 노드 root가 주어집니다. 이 트리를 중위 순회하여 나오는 노드 값들을 리스트에 저장하고, 그 리스트를 반환하세요.

 

예시:

만약 주어진 이진 트리가 다음과 같다고 가정하면:

    1
     \
      2
     /
    3

중위 순회를 수행하면 노드 값 [1, 3, 2] 순서대로 리스트에 저장하고 반환해야 합니다.

노트:

중위 순회를 재귀적으로 구현하거나 반복적으로 구현할 수 있습니다.
중위 순회를 수행하면 노드 값이 오름차순으로 나타납니다.
이 문제를 해결하기 위해서는 이진 트리의 중위 순회를 구현해야 합니다. 주어진 트리를 재귀적으로 순회하거나 스택을 사용하여 반복적으로 순회하는 방법을 사용할 수 있습니다.

 

public IList<int> InorderTraversal(TreeNode root) {
    List<int> list = new List<int>();
    InorderTraversalHelper(root, list);
    return list;
}

private void InorderTraversalHelper(TreeNode node, List<int> list) {
    if (node == null) {
        return;
    }
    
    InorderTraversalHelper(node.left, list); // 왼쪽 하위 트리 순회
    list.Add(node.val); // 현재 노드 처리
    InorderTraversalHelper(node.right, list); // 오른쪽 하위 트리 순회
}