Задача: 863. All Nodes Distance K in Binary Tree Сложность: medium Дан корень бинарного дерева, значение целевого узла target и целое число k. Верните массив значений всех узлов, которые находятся на расстоянии k от целевого узла. Ответ можно вернуть в любом порядке. Пример: Input: root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, k = 2 Output: [7,4,1] Explanation: The nodes that are a distance 2 from the target node (with value 5) have values 7, 4, and 1. 👨‍💻 Алгоритм: 1⃣Определите рекурсивную функцию add_parent(cur, parent), чтобы рекурсивно добавлять указатель на родителя к узлу cur. Если cur не пустой, добавьте указатель на parent: cur.parent = parent. Затем рекурсивно вызовите add_parent для левого и правого детей cur: add_parent(cur.left, cur) и add_parent(cur.right, cur). Вызовите add_parent(root, None), чтобы добавить все указатели на родителей (корневой узел не имеет родителя). 2⃣Инициализируйте пустой массив answer и пустое множество visited. Определите рекурсивную функцию dfs(cur, distance) для поиска всех узлов на расстоянии k от узла target. Если cur пустой или уже был посещён, вернитесь. Добавьте cur в visited, чтобы его не посещали повторно. Если distance = k, добавьте cur в answer и вернитесь. 3⃣Рекурсивно вызовите dfs для детей и родителя cur. Вызовите dfs(target, 0), чтобы найти все узлы на расстоянии k. Верните answer после завершения DFS. 😎 Решение: func distanceK(root, target TreeNode, k int) []int { addParent(root, nil) var answer []int visited := make(map[TreeNode]bool) dfs(target, k, visited, &answer) return answer } func addParent(cur, parent TreeNode) { if cur != nil { cur.parent = parent addParent(cur.Left, cur) addParent(cur.Right, cur) } } func dfs(cur TreeNode, distance int, visited map[TreeNode]bool, answer []int) { if cur == nil || visited[cur] { return } visited[cur] = true if distance == 0 { answer = append(answer, cur.Val) return } dfs(cur.parent, distance-1, visited, answer) dfs(cur.Left, distance-1, visited, answer) dfs(cur.Right, distance-1, visited, answer) } type TreeNode struct { Val int Left, Right TreeNode parent TreeNode } Ставь 👍 и забирай 📚 Базу знаний