Created
December 20, 2024 06:59
-
-
Save 8thgencore/01b1f2ab30cdb35380ab788a1f65ca64 to your computer and use it in GitHub Desktop.
103. Binary Tree Zigzag Level Order Traversal
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /* | |
| 103. Binary Tree Zigzag Level Order Traversal | |
| Описание: | |
| Дан корень бинарного дерева. Необходимо вернуть значения узлов в зигзагообразном порядке по уровням | |
| (то есть слева направо, затем справа налево для следующего уровня и так далее). | |
| Пример 1: | |
| 3 | |
| / \ | |
| 9 20 | |
| / \ | |
| 15 7 | |
| Вход: root = [3,9,20,null,null,15,7] | |
| Выход: [[3],[20,9],[15,7]] | |
| Пример 2: | |
| Вход: root = [1] | |
| Выход: [[1]] | |
| Пример 3: | |
| Вход: root = [] | |
| Выход: [] | |
| Ограничения: | |
| - Количество узлов в дереве: [0, 2000] | |
| - -100 <= Node.val <= 100 | |
| */ | |
| package main | |
| import "fmt" | |
| // TreeNode определяет структуру узла бинарного дерева | |
| type TreeNode struct { | |
| Val int | |
| Left *TreeNode | |
| Right *TreeNode | |
| } | |
| // buildTree создает тестовое дерево для демонстрации | |
| func buildTree() *TreeNode { | |
| return &TreeNode{ | |
| Val: 3, | |
| Left: &TreeNode{ | |
| Val: 9, | |
| }, | |
| Right: &TreeNode{ | |
| Val: 20, | |
| Left: &TreeNode{ | |
| Val: 15, | |
| }, | |
| Right: &TreeNode{ | |
| Val: 7, | |
| }, | |
| }, | |
| } | |
| } | |
| // zigzagLevelOrder выполняет зигзагообразный обход дерева по уровням | |
| func zigzagLevelOrder(root *TreeNode) (ans [][]int) { | |
| if root == nil { | |
| return | |
| } | |
| queue := []*TreeNode{root} | |
| level := 0 | |
| fmt.Printf("\nНачинаем обход дерева\n") | |
| for len(queue) > 0 { | |
| fmt.Printf("\n--- Уровень %d ---\n", level) | |
| fmt.Printf("Текущая очередь: ") | |
| for _, node := range queue { | |
| fmt.Printf("%d ", node.Val) | |
| } | |
| fmt.Printf("\n") | |
| t := []int{} | |
| currentLevelSize := len(queue) | |
| fmt.Printf("Размер текущего уровня: %d\n", currentLevelSize) | |
| // Обработка всех узлов текущего уровня | |
| for n := currentLevelSize; n > 0; n-- { | |
| node := queue[0] | |
| queue = queue[1:] | |
| t = append(t, node.Val) | |
| fmt.Printf("Обработка узла: %d\n", node.Val) | |
| // Добавление потомков в очередь | |
| if node.Left != nil { | |
| queue = append(queue, node.Left) | |
| fmt.Printf(" Добавлен левый потомок: %d\n", node.Left.Val) | |
| } | |
| if node.Right != nil { | |
| queue = append(queue, node.Right) | |
| fmt.Printf(" Добавлен правый потомок: %d\n", node.Right.Val) | |
| } | |
| } | |
| // Разворот значений для четных уровней | |
| if level%2 != 0 { | |
| fmt.Printf("Переворачиваем уровень: %v -> ", t) | |
| for i, j := 0, len(t)-1; i < j; i, j = i+1, j-1 { | |
| t[i], t[j] = t[j], t[i] | |
| } | |
| fmt.Printf("%v\n", t) | |
| } | |
| ans = append(ans, t) | |
| fmt.Printf("Результат после уровня %d: %v\n", level, ans) | |
| level++ | |
| } | |
| fmt.Printf("\nИтоговый результат: %v\n", ans) | |
| return | |
| } | |
| func main() { | |
| root := buildTree() | |
| result := zigzagLevelOrder(root) | |
| fmt.Printf("Результат обхода дерева: %v\n", result) | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment