[트리,재귀] LeetCode 226번 문제 학습

 

문제 설명

Invert Binary Tree는 이진 트리의 좌우 서브트리를 뒤집는 문제임.
각 노드의 왼쪽과 오른쪽 자식을 스왑해서 전체 트리를 반전시켜야 함.

예를 들어, 트리가 4(2(1,3),6(5,7))면 반전 후 4(6(7,5),2(3,1))이 됨. 입력은 TreeNode 구조체로 주어지고, 루트 노드를 받아 반전된 트리의 루트를 리턴하면 됨.

---

 

푼 과정

재귀로 풀었음. 루트가 nil이면 그대로 리턴. nil 아니면 현재 노드의 왼쪽과 오른쪽 자식을 temp 변수 써서 스왑함.
그 다음 왼쪽과오른쪽 서브트리를 재귀로 호출해서 각각 반전.

 

마지막에 루트 리턴. 코드 간단하고 트리 반전 로직 딱 맞췄음

package main

import (
)

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

func invertTree(root *TreeNode) *TreeNode {
	// root가 nil 이면 좌우 반전 없이 return
	if root == nil {
		return root
	}

	// 받은 root의 좌우를 반전
	temp_left := root.Left
	root.Left = root.Right
	root.Right = temp_left

	invertTree(root.Left)
	invertTree(root.Right)

	return root
}

func main() {
}