Invertir Un Árbol Binario (De Izquierda a Derecha)
Estaba mirando preguntas de entrevista y recientemente me encontré con una que le preguntó cómo revertir un árbol binario general, como voltearlo de derecha a izquierda.
Así que, por ejemplo, si tuviéramos el árbol binario
6
/ \
3 4
/ \ / \
7 3 8 1
Invertirlo crearía
6
/ \
4 3
/ \ / \
1 8 3 7
No he sido capaz de pensar en una buena implementación sobre cómo resolver este problema. ¿Alguien puede ofrecer buenas ideas?
Gracias
9 answers
Puede usar recursión:
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);
}
}
Basado en los comentarios:
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);
}
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2017-03-07 08:20:51
Invertir un árbol binario en 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;
}
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2016-07-25 13:59:25
Hay un par de partes interesantes a esta pregunta. En primer lugar, dado que su lenguaje es Java, es más probable que tenga un nodo genérico clase , algo así:
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;
}
....
}
En segundo lugar, invertir, a veces llamado invertir, se puede hacer mutando los campos izquierdo y derecho del nodo, o creando un nuevo nodo igual que el original pero con sus hijos izquierdo y derecho "invertidos."El primer enfoque se muestra en otra respuesta , mientras que el segundo el enfoque se muestra aquí:
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);
}
}
La idea de no mutar una estructura de datos es una de las ideas detrás de estructuras de datos persistentes, que son bastante interesantes.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2017-05-23 12:17:44
Hay muchas maneras por ahí para usted y mucha persona dirá hacer muchas nuevas respuestas, pero la mejor manera de resolver las preguntas del árbol(casi) con la ayuda de la recursión y el uso de esto se puede resolver cualquier otro problema relacionado con el árbol.
Así que aquí está la solución para usted que cómo se puede invertir el árbol binario -
Para eso lo que tendrá que hacer es que en cada paso tenemos que intercambiar hijo izquierdo y derecho del padre, así que use la función swap para intercambiar por hijo izquierdo y derecho y hacer este proceso también para sus hijos.
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 :)
}
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2015-06-13 04:18:12
Modifique el recorrido de pre-orden para voltear los nodos antes de continuar.
#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)
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2016-02-28 05:15:50
Puede intercambiar recursivamente los nodos izquierdo y derecho como se muestra a continuación;
// 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);
}
Código de demostración para Java
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;
}
}
}
Salida
Before invert
Tree;
*****
6
3 4
7 3 8 1
After invert
Tree;
*****
6
4 3
1 8 3 7
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2016-03-12 04:34:19
La función de recursión puede ser muy simple como se muestra a continuación:
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;
}
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2017-12-05 01:08:35
public class TreeNode
{
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) { val = x; }
}
public class Solution
{
public TreeNode root;
public TreeNode InvertTree(TreeNode root)
{
if (root == null)
return null;
Swap(root);
InvertTree(root.left);
InvertTree(root.right);
return root;
}
public void Swap(TreeNode root)
{
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
}
}
public class ReverseBinaryTree
{
public void Test()
{
Solution tree = new Solution();
tree.root = new TreeNode(1);
tree.root.left = new TreeNode(2);
tree.root.right = new TreeNode(3);
tree.root.left.left = new TreeNode(4);
tree.root.left.right = new TreeNode(5);
tree.InvertTree(tree.root);
Console.ReadLine();
}
}
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2018-01-16 15:03:32
He visto que la mayoría de las respuestas no se centran en problemas de puntero nulo.
public static Node invertBinaryTree(Node node) {
if(node != null) {
Node temp = node.getLeftChild();
node.setLeftChild(node.getRightChild());
node.setRigthChild(temp);
if(node.left!=null) {
invertBinaryTree(node.getLeftChild());
}
if(node.right !=null) {
invertBinaryTree(node.getRightChild());
}
}
return node;
}
En el código anterior estamos haciendo llamadas recursivas solo si el hijo izquierdo/derecho del nodo raíz no es null. Es uno de los enfoques más rápidos!
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2018-09-13 02:59:11