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

문제 설명

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

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

제약 조건

• 트리는 비어 있을 수도 있음 (root == nil).
• 노드 값은 정수(int)로 주어짐.
• 출력은 []int 슬라이스로, 순회 순서대로 값 담아서 리턴.

문제를 푼 과정

재귀

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).
   • 이 순서가 정확히 전위 순회 패턴(루트 → 왼쪽 → 오른쪽) 맞춤.
3. 포인터 사용
   • 슬라이스를 *[]int로 받아서 수정함. Go에서 슬라이스는 참조형이지만, append로 길이 바뀔 때 원본 슬라이스에 반영하려면 포인터 써야 안전함.
   • 이거 때문에 *list = append(*list, root.Val)로 값 추가한 거임.

전위 순회 특성 그대로 따라가면서 값을 쌓아가는 구조임. 

---

어떤 알고리즘 썼는지

트리 순회(Tree Traversal) 알고리즘, 그중에서도 전위 순회를 구현한 거임

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

package main

import (
	"os"
	"fmt"
	"bufio"
)

var (
	wr = bufio.NewWriter(os.Stdout)
	rd = bufio.NewReader(os.Stdin)
)

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)
	}
}

func main() {
	defer wr.Flush()

	// [1,2,3,4,5,null,8,null,null,6,7,9]
root := &TreeNode{Val: 1, Left: &TreeNode{Val: 2, Left: &TreeNode{Val: 4}, Right: &TreeNode{Val: 5}}, Right: &TreeNode{Val: 3, Right: &TreeNode{Val: 8, Left: &TreeNode{Val: 6}, Right: &TreeNode{Val: 7}}}}

	result := preorderTraversal(root)

	for i := 0; i < len(result); i++ {
		fmt.Fprintln(wr, result[i])
	}

}