[DFS-중위 순회] LeetCode 94번 문제 학습

 

재귀(Recursion)로 풀어보기

 

• 이진 트리의 중위 순회(Inorder Traversal) 정의 이해
  • 왼쪽 서브트리 → 현재 노드 → 오른쪽 서브트리 순서로 방문
• DFS(깊이 우선 탐색) 방식으로 순회를 구현
  • left 서브트리를 먼저 탐색
  • 현재 노드 값을 리스트에 추가
  • right 서브트리를 탐색
• Base Case(기저 조건) 설정
  • 노드가 nil이면 리턴

 

---

DFS(깊이 우선 탐색)를 이용한 중위 순회(Inorder Traversal) 방식

 

• 깊이 우선 탐색(DFS)은 한 방향으로 끝까지 내려간 후, 백트래킹(되돌아오면서 다른 경로 탐색)하는 방식
• 중위 순회(Inorder Traversal)는 DFS의 한 형태로, 노드를 방문하는 순서가 왼쪽 → 루트 → 오른쪽이 되는 DFS

 

package main

import "fmt"

type TreeNode struct {
	Val int 
	Left *TreeNode
	Right *TreeNode
}

func inorderTraversal(root *TreeNode) []int {
	var result []int

	var dfs func(node *TreeNode)

	dfs = func(node *TreeNode) {
		if node == nil {
			return
		}

		dfs(node.Left)
		result = append(result, node.Val)
		dfs(node.Right)
	}

	dfs(root)
	return result
}

func main() {
	// 예제 트리 생성:   1
	//                   \
	//                    2
	//                   /
	//                  3
	root := &TreeNode{1, nil, &TreeNode{2, &TreeNode{3, nil, nil}, nil}}

	// 중위 순회 실행
	fmt.Println(inorderTraversal(root)) // 출력: [1 3 2]
}

 

 

코드의 동작 방식

• DFS 방식으로 왼쪽 서브트리 끝까지 탐색
  • 왼쪽 자식이 있으면 계속 재귀 호출
• 더 이상 왼쪽 자식이 없으면 현재 노드를 방문
  • 현재 노드 값을 result 리스트에 저장
• 오른쪽 서브트리 탐색
  • 오른쪽 자식이 있으면 다시 DFS로 탐색

이 코드는 DFS(깊이 우선 탐색) 방식으로 구현된 중위 순회(Inorder Traversal)입니다. 중위 순회는 왼쪽 → 루트 → 오른쪽 순서로 노드를 방문하며, 재귀 호출을 통해 깊이 우선 탐색을 수행