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

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

이 문제는 이진 트리가 좌우 대칭인지 확인하는 것이 문제의 핵심.

기존 100번 문제는 두 트리를 동시에 내려가며 "같은지"를 확인하는 데 초점을 두었지만 지금은 거울 형식으로 대칭하는 지 확인하는 것인 핵심인 문제임

여전히 재귀적 DFS. 100번 문제와 비슷하지만, 비교 대상이 "동일성"이 아니라 "대칭성"이라서 자식 노드의 연결 방향이 반대인 점만 다르다는 것을 알고 풀면 됨

 

 

• "Symmetric Tree"는 트리가 거울 대칭인지 확인하는 문제. 즉, 루트의 왼쪽 서브트리와 오른쪽 서브트리가 서로 대칭이어야 함
• 예를 들어, 왼쪽 서브트리의 왼쪽 자식은 오른쪽 서브트리의 오른쪽 자식과 같아야 하고, 왼쪽 서브트리의 오른쪽 자식은 오른쪽 서브트리의 왼쪽 자식과 같아야 함

---

package main

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

func isMirror(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 isMirror(part1.Left, part2.Right) && isMirror(part1.Right, part2.Left)
}

func isSymmetric(root *TreeNode) bool {
	if root == nil {
		return true
	}
	return isMirror(root.Left, root.Right)
}

func main() {
}

 

기준 코드에서 Left, Right가 같은 지 재귀적으로 확인하는 방식만 추가하여 문제를 풀었음