TreeNode

 

TreeNode

TreeNode는 트리(Tree) 자료구조를 이루는 기본 단위입니다.

ListNode(연결 리스트의 노드)가 val + next 로 이루어져 있다면,
TreeNode는 다음과 같은 구성으로 되어 있습니다:

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;

  constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
    this.val = val ?? 0;
    this.left = left ?? null;
    this.right = right ?? null;
  }
}

 

즉, 노드 하나에

• 값(val)
• 왼쪽 자식(left)
• 오른쪽 자식(right)
  
  이 함께 들어 있는 구조체입니다.

그림으로 보면 이렇게 생겼습니다

      ┌───────────┐
      │    val    │
      ├───────────┤
      │ left ptr  │──▶ (왼쪽 자식 노드)
      │ right ptr │──▶ (오른쪽 자식 노드)
      └───────────┘

 

---

 

연결 리스트 노드(ListNode)와 비교

 

개념	ListNode	TreeNode
연결 수	next 1개	left, right 2개
구조 형태	직선형(사슬)	계층형(나무 형태)
이동 방법	next만 따라감	left, right 둘 다 탐색 가능

 

ListNode → "길"
TreeNode → "나무"

그래서 트리는 위에서 아래로 가지가 뻗어나갑니다.

 

 

---

TreeNode로 만들어지는 트리 구조

예를 들어 이런 트리가 있다면

      1
     / \
    2   3
   / \
  4   5

이 트리는 TreeNode들로 다음과 같이 구성됩니다:

Node(1).left = Node(2)
Node(1).right = Node(3)
Node(2).left = Node(4)
Node(2).right = Node(5)

각 노드는 자신의 왼쪽/오른쪽 자식을 가리키고 있어요.
그래서 부모 → 자식 관계가 자연스럽게 표현됩니다.

 

---

 

트리는 실제 많은 문제에서 등장합니다

• 이진 탐색 트리(Binary Search Tree)
• 힙(Heap)
• 균형 트리(AVL, Red-Black Tree)
• 디렉토리 구조(폴더 트리)
• 수식 트리(Expression Tree)
• LeetCode 대표 문제들: 경로 합, 직경, 깊이 계산 등

트리 구조를 이해하면 난이도 있는 문제들이 갑자기 쉬워집니다.

---

트리 탐색 방법 3가지

트리의 가장 핵심 탐색 방식 3가지입니다.

1) 전위 순회 (Preorder)

Root → Left → Right

• 예: 1, 2, 4, 5, 3

2) 중위 순회 (Inorder)

Left → Root → Right

• 예: 4, 2, 5, 1, 3
  → 이진 탐색 트리에서 정렬된 순서를 보장!

3) 후위 순회 (Postorder)

Left → Right → Root

• 예: 4, 5, 2, 3, 1

 

각 순회는 DFS(Depth-First Search) 방식입니다.

 

---

BFS(레벨 순서 탐색)

트리를 위에서 아래로, 왼쪽부터 오른쪽으로 탐색하는 방식:

1 → 2 → 3 → 4 → 5

• Queue를 사용합니다.

 

---

예제 1: 이진 트리의 최대 깊이

트리의 최대 깊이를 구하라.

예:

      1
     / \
    2   3
   /
  4

 

깊이 = 3

DFS 

function maxDepth(root: TreeNode | null): number {
  if (!root) return 0;

  const left = maxDepth(root.left);
  const right = maxDepth(root.right);

  return Math.max(left, right) + 1;
}

 

• 재귀로 왼쪽/오른쪽 깊이를 구함
• 더 깊은 값 + 1(자기 자신) 반환
• 가장 기본적인 트리 DFS 문제

 

---

예제2: 이진 트리의 합 경로 (Path Sum)

루트에서 리프까지 가는 경로 중, 합이 target인 것이 있는가?

예

      5
     / \
    4   8
   /
 11

코드

function hasPathSum(root: TreeNode | null, targetSum: number): boolean {
  if (!root) return false;

  if (!root.left && !root.right) {
    return root.val === targetSum;
  }

  return (
    hasPathSum(root.left, targetSum - root.val) ||
    hasPathSum(root.right, targetSum - root.val)
  );
}