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

문제 설명

Binary Tree Postorder Traversal는 이진 트리를 후위 순회(Postorder Traversal) 방식으로 탐색해서

노드 값들을 배열로 리턴하는 거임. 

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

문제를 푼 과정

Preorder 코드에서 순서만 바꿔서 깔끔하게 풀었음. 

1. 메인 함수 (postorderTraversal)
   • 빈 슬라이스 list := []int{} 만들어서 결과 저장할 준비.
   • postorder 헬퍼 함수 호출하면서 root랑 슬라이스 포인터(&list) 넘김.
   • 마지막에 list 리턴. 이 부분은 Preorder랑 똑같음.
2. 재귀 헬퍼 함수 (postorder)
   • root가 nil인지 체크. nil이면 아무것도 안 하고 리턴.
   • nil 아니면:
     • 왼쪽 서브트리 재귀 호출: postorder(root.Left, list).
     • 오른쪽 서브트리 재귀 호출: postorder(root.Right, list).
     • 현재 노드 값 추가: *list = append(*list, root.Val).
   • 이 순서가 후위 순회 패턴(왼쪽 → 오른쪽 → 루트) 딱 맞음.
   • Preorder랑 비교하면, 값 추가하는 타이밍만 맨 마지막으로 옮긴 거임.

---

어떤 알고리즘 썼는지

이 문제도 트리 순회(Tree Traversal) 알고리즘, 이번엔 후위 순회(Postorder Traversal) 썼음. 

1. 재귀(Recursion)
   • 후위 순회도 재귀로 푸는 게 제일 직관적임.
   • 각 노드에서:
     • 왼쪽 서브트리 먼저 탐색.
     • 오른쪽 서브트리 탐색.
     • 마지막으로 현재 노드 처리 (값 추가).
   • 재귀는 트리의 깊이만큼 스택 쌓으면서 동작.
   • 시간복잡도: O(n) (n은 노드 수, 모든 노드 한 번씩 방문).
   • 공간복잡도: O(h) (h는 트리 높이, 재귀 스택 때문).
2. 대안: 반복(Iterative) 방식
   • 스택 써서 후위 순회 구현 가능함. 근데 후위 순회는 스택 조작이 Preorder보다 좀 까다로움 (왼쪽, 오른쪽 다 탐색한 뒤 루트 처리해야 하니까).
   • 재귀가 코드 간단하고 이해 쉬워서 이 문제에선 재귀가 최적 선택임.

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 postorderTraversal(root *TreeNode) []int {
	list := []int{}
	postorder(root, &list)
	return list
}

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

func main() {
	defer wr.Flush()

	root := &TreeNode{Val: 1}
	root.Left = &TreeNode{Val: 2}
	root.Right = &TreeNode{Val: 3}
	root.Left.Left = &TreeNode{Val: 4}
	root.Left.Right = &TreeNode{Val: 5}

	fmt.Fprintln(wr, postorderTraversal(root))
}