Как изменить порядок двоичного дерева ⇐ JAVA

[Anonymous]

Узел двоичного дерева имеет идентификатор, левое и правое поддерево.

Код: Выделить всё

class Node{
public int id;
public Tree left;
public Tree right;
}

Обратите внимание, что структура данных двоичного дерева правильна тогда и только тогда, когда каждый узел является поддеревом ровно одного другого узла, за исключением корня, который не может быть поддеревом какого-либо другого узла.
Узлы X и Y связаны, если узел X указывает на узел Y как на свое левое или правое поддерево или если узел Y указывает на узел X как на свое левое или правое поддерево.
Узлы X и Y связаны, если узел X указывает на узел Y как на свое левое или правое поддерево.


Например, в на рисунке выше:
узлы 1 и 6 соединены,
узлы 4 и 5 соединены,
узлы 3 и 4 не соединены.
Дано идентификатор листа, мне нужно перекоренить двоичное дерево, изменив его корень на другой узел, который является листом.
Перевернутое дерево должно сохранять все соединения исходного дерева - если узлы X, Y соединены в исходном дереве, то узлы X, Y должны оставаться связанными в перекоренном дереве.
Порядок поддеревьев в перекоренном дереве не имеет значения. Другими словами, допустимо поменять местами левое и правое поддерево для каждого узла.
Примеры:

• Дано дерево T, как описано на первом изображении выше, и Leaf_id = 2, функция должна вернуть дерево, показанное на втором изображении выше. Порядок поддеревьев не имеет значения, поэтому возвращаем

[img]https://i.sstatic .net/lQibF3R9.png[/img]

Это был вопрос для собеседования, мне удалось решить только некоторые примеры тестовых примеров, для скрытых тестовых примеров и тестов производительности это не удалось.
Вот мой код, который я пробовал на собеседовании и который прошел только типовые тестовые случаи:

Код: Выделить всё

import java.util.HashMap;
import java.util.*;

class Node {
public int id;  // Node ID
public Node left; // Left child
public Node right; // Right child
Node(int id) {
this.id = id;
}
public String toString() {
return "" + id;
}
}

class Main {
static void printTreeLevelOrder(Node root) {
if (root == null) return;

Queue nodeQueue = new LinkedList();
nodeQueue.add(root);

while (!nodeQueue.isEmpty()) {
Node currentNode = nodeQueue.poll();
System.out.print(currentNode.id + " ");
if (currentNode.left != null) nodeQueue.add(currentNode.left);
if (currentNode.right != null) nodeQueue.add(currentNode.right);
}
}

static void printTree(Node root) {
if (root == null) return;
System.out.print(root.id + " ");
printTree(root.left);
printTree(root.right);
}

public static void main(String[] args) {
// Create the example tree
Node rootNode = new Node(3);
rootNode.left = new Node(1);
rootNode.right = new Node(5);
rootNode.left.left = new Node(2);
rootNode.left.right = new Node(6);
rootNode.right.left = new Node(4);

int targetLeafId = 2;
Node newRoot = reRootTree(rootNode, targetLeafId);
printTree(newRoot);
}

public static Node reRootTree(Node T, int targetLeafId) {
// Map to store parent relationships
Map parentRelations = new HashMap();

// Find the leaf node and populate the parent map
Node targetLeafNode = locateLeafAndPopulateParentRelations(T, null, targetLeafId, parentRelations);

if (targetLeafNode == null) return null;  // targetLeafId not found in the tree

// Reroot the tree starting from the leaf node
Node newRootNode = adjustTree(T, targetLeafNode, parentRelations);

return newRootNode;
}

private static Node locateLeafAndPopulateParentRelations(Node currentNode, Node parentNode, int targetLeafId, Map parentRelations) {
if (currentNode == null) return null;

// Populate parent map
parentRelations.put(currentNode, parentNode);

// Check if this node is the leaf we're looking for
if (currentNode.id == targetLeafId) return currentNode;

// Recurse into left and right subtrees
Node leftSearch = locateLeafAndPopulateParentRelations(currentNode.left, currentNode, targetLeafId, parentRelations);
if (leftSearch != null) return leftSearch;

Node rightSearch = locateLeafAndPopulateParentRelations(currentNode.right, currentNode, targetLeafId, parentRelations);
return rightSearch;
}

private static Node adjustTree(Node root, Node leaf, Map parentRelations) {
Node currentNode = leaf;
Node previousNode = null;

// Traverse up from leaf to root, rerooting connections
while (currentNode != root) {
Node parentNode = parentRelations.get(currentNode);
Node originalLeftChild = currentNode.left;
Node originalRightChild = currentNode.right;

// Update left and right connections for current node
if (originalLeftChild != previousNode) {
currentNode.left = parentNode;    // Attach parent as new left
currentNode.right = originalRightChild; // Preserve original right
} else {
currentNode.right = parentNode;    // Attach parent as new right
currentNode.left = originalLeftChild;   // Preserve original left
}

// Remove the connection from the parent to this node to avoid cycles
if (parentNode != null) {
if (parentNode.left == currentNode) parentNode.left = null;
else if (parentNode.right == currentNode) parentNode.right = null;
}

previousNode = currentNode;
currentNode = parentNode;
}

return leaf;
}
}

Каков правильный подход к решению этой проблемы?

Подробнее здесь: https://stackoverflow.com/questions/791 ... inary-tree