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)의 한 형태로 볼 수 있다.
| 전위 순회 (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