[재귀,반복문] LeetCode 144번 문제 학습

문제 설명

Binary Tree Preorder Traversal는 이진 트리(Binary Tree)를 전위 순회(Preorder Traversal) 방식으로 탐색해서 노드 값들을 배열로 리턴하는 문제임. 전위 순회는:

• 루트(Root) → 왼쪽 서브트리(Left) → 오른쪽 서브트리(Right) 순서로 방문하는 거.

문제를 푼 과정

1. 메인 함수 (preorderTraversal)
   • 빈 슬라이스 list := []int{} 만들어서 결과 저장할 준비함.
   • preOrder라는 헬퍼 함수 호출하면서 root랑 슬라이스 포인터(&list) 넘김.
   • 마지막에 list 리턴. 이게 최종 답임.
2. 재귀 헬퍼 함수 (preOrder)
   • root가 nil이 아닌지 체크. nil이면 아무것도 안 하고 리턴.
   • nil 아니면:
     • 현재 노드 값(root.Val)을 슬라이스에 추가: *list = append(*list, root.Val).
     • 왼쪽 서브트리 재귀 호출: preOrder(root.Left, list).
     • 오른쪽 서브트리 재귀 호출: preOrder(root.Right, list).
   • 이 순서가 정확히 전위 순회 패턴(루트 → 왼쪽 → 오른쪽) 맞춤.

---

어떤 알고리즘 썼는지

이 문제는 트리 순회(Tree Traversal) 알고리즘, 전위 순회(Preorder Traversal)를 구현한 거임.

1. 재귀(Recursion)
   • 전위 순회는 재귀로 푸는 게 가장 자연스러움.
   • 각 노드에서:
     • 현재 노드 처리 (값 추가).
     • 왼쪽 서브트리 재귀 호출.
     • 오른쪽 서브트리 재귀 호출.
   • 재귀는 트리의 깊이만큼 스택을 쌓으면서 동작함.
   • 시간복잡도: O(n) (n은 노드 수, 모든 노드 한 번씩 방문).
   • 공간복잡도: O(h) (h는 트리 높이, 재귀 스택 때문).
2. 대안: 반복(Iterative) 방식
   • 재귀 대신 스택(Stack) 써서 풀 수도 있음. 스택에 오른쪽 노드 먼저 넣고 왼쪽 노드 나중에 넣어서 순서 맞춤.
   • 근데 재귀가 코드도 간단하고 이해하기 쉬워서 이 문제에선 재귀가 딱임.

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

func preorderTraversal(root *TreeNode) []int {
	list := []int{}
	preOrder(root, &list)
	return list
}

func preOrder(root *TreeNode, list *[]int) {
	if root != nil {
		*list = append(*list, root.Val)
		preOrder(root.Left, list)
		preOrder(root.Right, list)
	}
}