LeetCode에서 Binary Tree Inorder Traversal 문제 풀어보기

문제 링크

bookmark

트리란?

• 계층 구조를 표현할때 사용하는 자료 구조
• 뿌리(root)에서 가지처럼 뻗어나가는 형태의 자료 구조
• 트리 크기가 N일시 간선은 N-1 개이다

트리 용어

• 루트 노드 : 완전 최상위의 노드
• 단말 노드 : 자식이 없는 노드
• 크기 : 트리가 가지고 있는 모든 노드의 개수
• 깊이 : 루트 노드부터의 거리
• 높이 : 깊이중 최대값
• 차수 : 각 노드들의 간선 개수

트리의 순회

• 트리 자료구조에 포함된 노드를 특정한 방법으로 방문하는 방법
  • 트리의 정보를 시각적으로 확인이 가능

대표적인 순회 방법

• 전위 순회 : 루트를 먼저 방문
• 중위 순회 : 왼쪽 자식을 방문 하고 루트를 방문
• 후위 순회: 오른쪽 자식을 방문하고 루트를 방문

소스 코드

// 중위 순회이므로 left가 먼저
function inorderTraversal(root: TreeNode | null): number[] {
    let stack = [];
    let result = [];
    while(root !== null || stack.length !== 0) {
        while(root !== null) {
            stack.push(root);
            root = root.left;
        }
        
        root = stack.pop();
        result.push(root.val);
        root = root.right;
    }
    
    return result;
};

• stack 메모리와 result 배열을 만든다
• 트리를 받아 탐색해야하므로 while문을 선언한다
• 첫번째는 일단 현재 root를 stack에 넣는다
• 그리고 왼쪽 노드를 root로 갱신한다
• 그 노드가 null값이면 스택메모리해서 root를 꺼내어 value값을 결과에 push한다
• 그리고 오른쪽 노드 탐색을 위해 right를 root로 갱신한다
• root가 null이 되거나 stack메모리가 비어질때까지 같은 과정을 반복한다

즉 플로우를 글로 나타내면

[ [1,null,2,3] ] → left가 null 2번째 while문을 빠져나와 stack에서 pop을 한 후 root.val 인 1을 푸쉬 → right 값을 넣어 root가 [2,3]으로 변하고 [[2,3]] 형태로 stack에 push 됨 → left인 3이 있으므로 한번 더 push가 되어 총 stack 메모리는 [[2,3],[3]] 형태가 됨 → pop이 이루어지면 val인 3이 push → 한번 더 pop이 이루어지면 2가 push → stack메모리가 비어졌으므로 반복문 종료 → 즉 결과 값은 [1,3,2] 가 리턴