이진 트리를 뒤집는 golang 프로그램을 구현하는 방법

Flip Binary Tree golang

이진 트리 뒤집기는 고전적인 알고리즘 질문이며 인터뷰에서 자주 묻는 질문입니다. 이 기사에서는 이진 트리를 뒤집는 golang 프로그램을 구현합니다.

이진 트리란 무엇입니까

이진 트리는 루트 노드를 포함하여 제한된 노드 집합으로 구성된 트리 구조이며, 각 노드는 각각 왼쪽 및 오른쪽 자식 노드에 연결됩니다. 모든 노드에 왼쪽 또는 오른쪽 자식 노드가 없는 경우 트리 구조를 이진 트리라고 합니다.

golang에서는 구조가 이진 트리 노드를 나타내는 데 자주 사용됩니다. 예:

type TreeNode struct {

Val int
Left *TreeNode
Right *TreeNode

}

위 코드를 사용하여 이진 트리 노드를 정의합니다. 여기서 Val은 노드의 값을 나타내고 Left는 왼쪽 자식 노드를 나타내고 Right는 오른쪽 자식 노드를 나타냅니다. .

이진 트리를 뒤집는 방법

이진 트리를 뒤집는 문제는 간단해 보이지만 실제로는 몇 가지 복잡한 문제가 수반됩니다. 설명의 편의를 위해 다음과 같은 이진 트리가 있다고 가정합니다.

4
/
2 7

 / \
6   9

뒤집은 후 이진 트리는 다음과 같아야 합니다.

 4

/
7 2
/
9 6

코드 구현 측면에서 재귀적 방법을 사용하여 이 문제를 해결할 수 있습니다. 재귀적 방법은 구조의 포인터를 직접 사용하여 왼쪽 및 오른쪽 자식 노드의 위치를 ​​교환할 수 있습니다. 재귀적 방법의 코드는 다음과 같습니다.

func invertTree(root TreeNode) TreeNode {

if root == nil {
    return nil
}

root.Left, root.Right = invertTree(root.Right), invertTree(root.Left)
return root

}

이진 트리의 루트 노드 포인터를 매개변수로 받아 반환하는 invertTree라는 함수를 선언했습니다. 뒤집힌 새 이진 트리에 대한 전달된 포인터입니다. 루트 노드가 비어 있으면 nil이 반환됩니다.

함수 본문 내에서 재귀를 사용하여 이진 트리를 뒤집는 프로세스를 완료합니다. 루트 노드의 왼쪽 자식 노드와 오른쪽 자식 노드를 교환한 다음 이 프로세스를 자식 노드에 재귀적으로 적용합니다.

마지막으로 새로운 뒤집힌 이진 트리의 루트 노드 포인터를 반환합니다.

전체 코드는 다음과 같습니다:

package main

import "fmt"

type TreeNode struct {

Val int
Left *TreeNode
Right *TreeNode

}

func invertTree(root TreeNode) TreeNode {

if root == nil {
    return nil
}

root.Left, root.Right = invertTree(root.Right), invertTree(root.Left)
return root

}

f unc 메인 () {

root := &TreeNode{Val: 4, Left: &TreeNode{Val: 2},
    Right: &TreeNode{Val: 7, Left: &TreeNode{Val: 6}, 
           Right: &TreeNode{Val: 9}}}

fmt.Println("Before invert: ")
fmt.Println(root.Val, root.Left.Val, root.Right.Val, root.Right.Left.Val, root.Right.Right.Val)

invertTree(root)

fmt.Println("After invert: ")
fmt.Println(root.Val, root.Left.Val, root.Right.Val, root.Left.Left.Val, root.Left.Right.Val)

}

이 예에서는 먼저 이진 트리의 루트 노드를 정의합니다. 메인 함수에서는 invertTree 함수를 호출하여 이진 트리를 뒤집습니다. 마지막으로 뒤집기 전후의 이진 트리를 인쇄합니다.

결론

이 기사에서는 이진 트리를 뒤집는 방법에 대한 golang 프로그램을 보여주었습니다. 간단한 재귀 함수를 사용함으로써 우리 프로그램은 이 문제를 매우 잘 해결할 수 있습니다. 이 글이 모든 사람이 이진 트리 뒤집기와 golang 언어 사용의 문제를 이해하는 데 도움이 되기를 바랍니다.

위 내용은 이진 트리를 뒤집는 golang 프로그램을 구현하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!