← 14주차 · 트리와 이진 트리
쉬움트리DFS재귀

중위 순회

이진 트리의 루트 root가 주어져요. 중위 순회(inorder) 순서로 방문한 노드 값을 배열로 반환해요.

중위 순회는 각 노드에서 왼쪽 서브트리 → 자기 자신 → 오른쪽 서브트리 순으로 내려가요. 이 순서가 중요한 이유는 이진 탐색 트리를 중위 순회하면 값이 정렬된 채로 나오기 때문이에요.

트리는 레벨 순서 배열로 주어져요. null은 자식이 없다는 뜻이고, 채점기가 이 배열을 노드로 바꿔서 root로 넘겨줘요. 노드는 val, left, right를 가지며, 새 노드가 필요하면 TreeNode로 만들 수 있어요.

예시

예시 1
입력
root = [1, null, 2, 3]
출력
[1, 3, 2]
설명
1의 왼쪽은 비었으니 1을 먼저 방문하고, 오른쪽 서브트리(2)로 가서 그 왼쪽 자식 3을 먼저 방문해요.
예시 2
입력
root = [4, 2, 6, 1, 3, 5, 7]
출력
[1, 2, 3, 4, 5, 6, 7]
설명
이진 탐색 트리라 정렬된 순서로 나와요.
예시 3
입력
root = []
출력
[]

제한 사항

  • 노드 개수는 0개 이상 10,000개 이하예요.
  • -1,000 ≤ node.val ≤ 1,000
결과 배열 하나를 만들어두고, 재귀 함수 안에서 왼쪽을 먼저 처리하고 자기 값을 넣은 다음 오른쪽을 처리해요. 세 줄의 순서가 곧 순회 이름이에요.
javascript
function inorderTraversal(root) {
  const out = [];
  const walk = (node) => {
    if (node === null) return;
    walk(node.left);
    out.push(node.val);
    walk(node.right);
  };
  walk(root);
  return out;
}
이전 문제트리의 최대 깊이
다음 문제트리 뒤집기
에디터를 불러오고 있어요…
코드를 작성하고를 눌러 예시 테스트를 확인해 보세요.