99클럽 코테 스터디 17일차 TIL - Binary Tree Inorder Traversal

---

Binary Tree Inorder Traversal

출처 : LeetCode

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

Example 1:

Input: root = [1,null,2,3]
Output: [1,3,2]

Example 2:
Input: root = []
Output: []

Example 3:
Input: root = [1]
Output: [1]
 
Constraints:

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

---

 

오늘도 즐거운 리트코드 문제풀이 시간이다.
배열 문제를 주로 풀다가 트리 문제를 접하게 되니 접근 방식이 달라서 어렵게 느껴진다.

 

이진 트리 순회

이진 트리 순회(traversal) 방법에는 여러 가지가 있으며, 가장 일반적인 세 가지는 다음과 같다: 전위 순회(Preorder), 중위 순회(Inorder), 후위 순회(Postorder). 각 순회 방법은 노드를 방문하는 순서가 다르다.  깊이 우선 탐색(Depth-First Traversal, DFT)의 한 형태로 볼 수 있다.

 

출처 : https://ko.wikipedia.org/wiki/%ED%8A%B8%EB%A6%AC_%EC%88%9C%ED%9A%8C

전위 순회 (Preorder)	루트 노드 -> 왼쪽 서브트리 -> 오른쪽 서브트리	F, B, A, D, C, E, G, I, H
중위 순회 (Inorder) 대칭 순회(symmetric traversal)	왼쪽 서브트리 -> 루트 노드 -> 오른쪽 서브트리	A, B, C, D, E, F, G, H, I
후위 순회 (Postorder)	왼쪽 서브트리 -> 오른쪽 서브트리 -> 루트 노드	A, C, E, D, B, H, I, G, F

 

중위 순회의 경우 그림으로 그려보면 다음과 같다.

왼쪽 서브트리 → 가운데 루트노드 → 오른쪽 서브트리를 순서대로 순회하는데, 위 트리에서 루트노드는 F이므로 F의 왼쪽 자식노드인 B, 다음으로는 B의 왼쪽 서브트리인 A를 찾아간다. 방문은 F→ B → A로 하여 결과값 배열에는 A부터 담긴다. 

 

풀이

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */

// 1. 왼쪽 서브 트리를 중위 순회한다.
// 2. Root 노드를 방문한다.
// 3. 오른쪽 서브 트리를 중위 순회한다.

var inorderTraversal = function(root) {
    // 1. 결과를 저장할 배열을 생성
    let results = [];

    // 2. 노드를 순회하는 함수 traverse 생성
    const traverse = (node) => {
        // a. 현재 노드가 null이면 함수 종료
        if (node === null) return;

        // b. 현재 노드의 왼쪽 서브트리 존재시 순회
        if (node.left) traverse(node.left);

        // c. 현재 노드 값을 결과 배열에 넣기
        results.push(node.val);

        // d. 현재 노드의 오른쪽 서브트리 존재시 순회
        if (node.right) traverse(node.right);
    }
    // 3. 루트 노드에서 순회를 시작
    traverse(root);

    return results;
};

 

참고 링크

https://ko.wikipedia.org/wiki/%ED%8A%B8%EB%A6%AC_%EC%88%9C%ED%9A%8C

https://www.youtube.com/watch?v=UCEqukCH5Tw