Я смотрел на вопросы интервью, и недавно я натолкнулся на того, кто спросил, как изменить общее двоичное дерево, например, перевернуть его справа налево.
Так, например, если бы мы имели двоичное дерево
6
/ \
3 4
/ \ / \
7 3 8 1
Реверсирование создаст
6
/ \
4 3
/ \ / \
1 8 3 7
Я не смог придумать хорошую реализацию того, как решить эту проблему. Может ли кто-нибудь предложить хорошие идеи?
Спасибо
Вы можете использовать рекурсию:
static void reverseTree(final TreeNode root) {
final TreeNode temp = root.right;
root.right = root.left;
root.left = temp;
if (root.left != null) {
reverseTree(root.left);
}
if (root.right != null) {
reverseTree(root.right);
}
}
Основываясь на комментариях:
static void reverseTree(final TreeNode root) {
if (root == null) {
return;
}
final TreeNode temp = root.right;
root.right = root.left;
root.left = temp;
reverseTree(root.left);
reverseTree(root.right);
}
Есть пара интересных частей к этому вопросу. Во-первых, поскольку ваш язык Java, вы, скорее всего, будете иметь общий класс Node, что-то вроде этого:
class Node<T> {
private final T data;
private final Node left;
private final Node right;
public Node<T>(final T data, final Node left, final Node right) {
this.data = data;
this.left = left;
this.right = right;
}
....
}
Во-вторых, обратное, иногда называемое инвертированием, может быть выполнено либо путем изменения левого и правого полей node, либо путем создания нового Node, как и оригинал, но с его левыми и правыми дочерними элементами "." Первый подход показан в другом ответе, в то время как второй подход показан здесь:
class Node<T> {
// See fields and constructor above...
public Node<T> reverse() {
Node<T> newLeftSubtree = right == null ? null : right.reverse();
Node<T> newRightSubtree = left == null ? null : left.reverse();
return Node<T>(data, newLeftSubtree, newRightSubtree);
}
}
Идея не мутировать структуру данных - одна из идей постоянных структур данных, которые довольно интересны.
Обратное двоичное дерево в O (1).
struct NormalNode {
int value;
struct NormalNode *left;
struct NormalNode *right;
};
struct ReversedNode {
int value;
struct ReversedNode *right;
struct ReversedNode *left;
};
struct ReversedNode *reverseTree(struct NormalNode *root) {
return (struct ReversedNode *)root;
}
Есть много способов для вас, и многие люди скажут много новых ответов, но лучший способ решить вопросы дерева (почти) с помощью рекурсии и используя это, вы можете решить любые другие проблемы, связанные с деревом.
Итак, вот вам решение, что вы можете изменить двоичное дерево -
Для этого вам нужно будет на каждом шагу поменять левый и правый дочерние элементы родителя, поэтому используйте функцию swap для замены для левого и правого дочерних элементов и выполните этот процесс для своих детей.
void reversetree(struct node* head)
{
//first check for the exception whether does it even exit or not
if(head==NULL)
return ;
reversetree(head->left); //reverse call for left child
reversetree(head->right); //same reverse call for right child
//now next these steps will swap the children
struct node* temp=head->left;
head->left=head->right;
head->right=head->left;
//now exit the function and you are done :)
}
Измените предварительный обход, чтобы перевернуть узлы перед тем, как пройти дальше.
#python3
def flipTree(node):
if node is None:
return
#flip nodes
node.left,node.right = node.right,node.left
flipTree(node.left)
flipTree(node.right)
Вы можете рекурсивно обменивать левый и правый узлы, как показано ниже:
// helper method
private static void reverseTree(TreeNode<Integer> root) {
reverseTreeNode(root);
}
private static void reverseTreeNode(TreeNode<Integer> node) {
TreeNode<Integer> temp = node.left;
node.left = node.right;
node.right = temp;
if(node.left != null)
reverseTreeNode(node.left);
if(node.right != null)
reverseTreeNode(node.right);
}
import java.util.LinkedList;
import java.util.Queue;
public class InvertBinaryTreeDemo {
public static void main(String[] args) {
// root node
TreeNode<Integer> root = new TreeNode<>(6);
// children of root
root.left = new TreeNode<Integer>(3);
root.right = new TreeNode<Integer>(4);
// grand left children of root
root.left.left = new TreeNode<Integer>(7);
root.left.right = new TreeNode<Integer>(3);
// grand right childrend of root
root.right.left = new TreeNode<Integer>(8);
root.right.right = new TreeNode<Integer>(1);
System.out.println("Before invert");
traverseTree(root);
reverseTree(root);
System.out.println("\nAfter invert");
traverseTree(root);
}
// helper method
private static void reverseTree(TreeNode<Integer> root) {
reverseTreeNode(root);
}
private static void reverseTreeNode(TreeNode<Integer> node) {
TreeNode<Integer> temp = node.left;
node.left = node.right;
node.right = temp;
if(node.left != null)
reverseTreeNode(node.left);
if(node.right != null)
reverseTreeNode(node.right);
}
// helper method for traverse
private static void traverseTree(TreeNode<Integer> root) {
Queue<Integer> leftChildren = new LinkedList<>();
Queue<Integer> rightChildren = new LinkedList<>();
traverseTreeNode(root, leftChildren, rightChildren);
System.out.println("Tree;\n*****");
System.out.printf("%3d\n", root.value);
int count = 0;
int div = 0;
while(!(leftChildren.isEmpty() && rightChildren.isEmpty())) {
System.out.printf("%3d\t%3d\t", leftChildren.poll(), rightChildren.poll());
count += 2;
div++;
if( (double)count == (Math.pow(2, div))) {
System.out.println();
count = 0;
}
}
System.out.println();
}
private static void traverseTreeNode(TreeNode<Integer> node, Queue<Integer> leftChildren, Queue<Integer> rightChildren) {
if(node.left != null)
leftChildren.offer(node.left.value);
if(node.right != null)
rightChildren.offer(node.right.value);
if(node.left != null) {
traverseTreeNode(node.left, leftChildren, rightChildren);
}
if(node.right != null) {
traverseTreeNode(node.right, leftChildren, rightChildren);
}
}
private static class TreeNode<E extends Comparable<E>> {
protected E value;
protected TreeNode<E> left;
protected TreeNode<E> right;
public TreeNode(E value) {
this.value = value;
this.left = null;
this.right = null;
}
}
}
Before invert
Tree;
*****
6
3 4
7 3 8 1
After invert
Tree;
*****
6
4 3
1 8 3 7
Функция рекурсии может быть очень простой, как показано ниже:
public Node flipTree(Node node) {
if(node == null) return null;
Node left = flipTree(node.left);
Node right = flipTree(node.right);
node.left = right;
node.right = left;
return node;
}