[DFS - 재귀] LeetCode 100번 문제 학습

 

DFS를 기반으로 한 재귀적 알고리즘

트리의 루트부터 시작해서 왼쪽과 오른쪽 자식으로 깊이 들어가며 비교하니까, 깊이를 우선적으로 탐색하는 DFS의 특성을 따르고 있음. 

트리 비교를 위한 재귀적 DFS로 문제를 풀었음

---

 

두 개의 이진 트리가 다른 지 비교하는 문제.

 

DFS-중위 순회를 통해 결과 값이 다른 지 같은 지 비교하는 방식으로 구현을 하려고 하였으나.

 

• 구조적 동일성 확인의 한계: 중위순회는 노드 방문 순서만 기록하니까, 트리의 구조가 다르더라도 우연히 값의 순서가 같게 나올 가능성이 있음. 예를 들어, 한쪽 트리는 왼쪽 서브트리만 있고 다른 쪽은 오른쪽 서브트리만 있는 경우, 중위순회 결과가 동일할 수 있는데 실제로는 구조가 다름
• 추가 검증 필요: "Same Tree" 문제는 값뿐만 아니라 구조도 완전히 같아야 하니까, 중위순회만으로는 충분하지 않을 수 있음. 예를 들어, 널 노드(null)의 위치를 명시적으로 체크하지 않으면 구조적 차이를 놓칠 수 있음.

결론적으로, 중위순회 결과만 비교하는 건 완전한 해결책은 아니야. 구조적 동일성을 보장하려면 재귀적으로 노드마다 직접 비교하거나, 널 노드를 결과에 포함시키는 식으로 보완해야 함

 

 

"Same Tree" 문제를 정확히 풀기 위해서는 중위순회(Inorder Traversal)처럼 순회 결과를 배열로 만들어 비교하는 방식 대신, 트리의 각 노드를 직접 재귀적으로 비교하는 DFS(깊이 우선 탐색) 접근법을 사용하는 게 가장 적합하는 생각이 듦

 

이 문제는 두 트리의 구조와 값이 모두 동일한지 확인해야 하니까, 노드 단위로 바로 비교하는 게 더 직관적이고 확실함

 

---

구체적으로는

• 재귀적 노드 비교: 두 트리의 루트부터 시작해서, 각 노드의 값과 왼쪽/오른쪽 자식을 재귀적으로 비교하는 방식.
• 종료 조건: 노드가 널(null)인지 확인하고, 두 트리의 대응되는 노드가 모두 널이거나 값이 같은지를 체크.

이 방식은 중위순회처럼 순회 결과를 따로 저장하지 않고, 트리를 탐색하면서 즉시 비교하기 때문에 구조와 값의 동일성을 보장함

 

중위순회는 순서만 기록해서 구조적 차이를 놓칠 수 있었던 반면, 이 방법은 노드의 위치와 값을 동시에 확인하니까 문제 요구사항에 맞을 듯 함

 

---

기존에 공부했던 중위순회(Inorder Traversal)만 알고 있어도 재귀적 비교를 이해하는 데 충분한 기반이 되기 때문에,  "Same Tree" 문제를 풀기 위한 재귀적 비교는 사실 중위순회처럼 특정 순서를 따르는 게 아니라, 두 트리의 노드를 동시에 내려가면서 비교하는 방식을 사용

 

func isSameTree(part1, part2 *TreeNode) bool {
	if part1 == nil && part2 == nil {
		return true
	}
	if part1 == nil || part2 == nil {
		return false
	}
	if part1.Val != part2.Val {
		return false
	}
	return isSameTree(part1.Left, part2.Left) && isSameTree(part1.Right, part2.Right)
}

 

• 함수 시작: isSameTree(p, q)라고 가정
• 조건 1: p == nil && q == nil → 참 반환 (둘 다 끝에 도달).
• 조건 2: p == nil || q == nil → 거짓 반환 (한쪽만 끝남).
• 조건 3: p의 값 != q의 값 → 거짓 반환 (값 다름).
• 재귀: 왼쪽 비교 isSameTree(p.Left, q.Left)와 오른쪽 비교 isSameTree(p.Right, q.Right) 결과를 합쳐서 반환.

중위순회와의 차이점은, 중위순회는 왼쪽-노드-오른쪽 순으로 값을 모으는 데 초점이 맞춰져 있다면, 여기서는 두 트리를 동시에 내려가며 "같은지"를 확인하는 데 초점이 맞춰져 있다는 것임