[leetcode]94. Binary Tree Inorder Traversal

Mayton·2022년 6월 14일

CodeTest leetcode

Coding-Test

목록 보기

7/37

BinaryTreeInOrderTraversal

문제

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]
```

제한사항

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

기본지식

이진트리

이진 트리는 Data Structure의 트리 구조 중 자식 노드가 두개인 트리를 의미한다. 한편, 이진 트리는 자료의 삽입, 삭제 방법에 따라 정 이진 트리(Full binary tree), 완전 이진 트리(Complete binary tree), 포화 이진 트리(Perfect binary tree)로 나뉜다.

[1,2,3,4,5,6,7]과 같은 array로 나타내기는 한다.

정 이진 트리: 각 노드가 0 개 혹은 2 개의 자식 노드를 갖는 경우
완전 이진 트리: 마지막 레벨을 제외한 모든 노드가 가득 차 있어야 하고, 마지막 레벨의 노드는 전부 차 있지 않아도 되지만 왼쪽이 채워져 있는 경우
포화 이진 트리: 정 이진 트리이면서 완전 이진 트리인 경우. 모든 리프 노드의 레벨이 동일하고, 모든 레벨이 가득 채워져 있어야 됨.

Inorder Traversal (중위순회)

중위, 후위, 전위란 root의 위치가 어디에 있느냐를 말한다. 중위는 root는 중간, 나머지는 항상 왼쪽 ->오른 쪽 순으로 순회된다.

중위 순회(inorder traversal)
왼쪽 서브트리 -> 루트 -> 오른쪽 서브트리
루트 노드가 가운데에 온다.

후위 순회(postorder traversal)
왼쪽 서브트리 -> 오른쪽 서브트리 -> 루트
루트 노드가 후위에 온다.

전위 순회(preorder traversal)
루트 -> 왼쪽 -> 오른쪽
루트 노드가 맨 앞에 온다.

풀이

function solution(root) {
  let result = [];
  dfs(root);

  function dfs(root) {

    if (root != null) {
      dfs(root.left);
      result.push(root.val);
      dfs(root.right);
    }
  }
  return result;
}