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

문제 링크

https://leetcode.com/problems/binary-tree-inorder-traversal/

트리란?

계층 구조를 표현할때 사용하는 자료 구조

뿌리(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] 가 리턴