java - programar - Invertir un árbol binario(de izquierda a derecha)
grado de un arbol (8)
Hay muchas maneras para ti y muchas personas dirán muchas nuevas respuestas, pero la mejor manera de resolver preguntas de árbol (casi) con la ayuda de la recursión y al usar esto puedes resolver cualquier otro problema relacionado con el árbol.
Así que aquí está la solución para ti, ¿cómo puedes invertir el árbol binario?
Para eso, lo que tendrá que hacer es en cada paso que tengamos que intercambiar el hijo izquierdo y derecho del padre, así que use la función de intercambio para intercambiar el hijo izquierdo y el derecho y también haga este proceso 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 :)
}
Estaba viendo las preguntas de la entrevista y recientemente encontré una que le preguntó cómo invertir un árbol binario general, como voltearlo de derecha a izquierda.
Entonces, 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 podido pensar en una buena implementación sobre cómo resolver este problema. ¿Alguien puede ofrecer alguna buena idea?
Gracias
Hay un par de partes interesantes en esta pregunta. En primer lugar, dado que su idioma es Java, es más probable que tenga una clase Node genérica, algo como esto:
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 inversión, se puede hacer ya sea mutando los campos izquierdo y derecho del nodo, o creando un nuevo nodo como el original pero con sus hijos izquierdo y derecho "invertidos". El primer enfoque se muestra en otra respuesta , mientras que el segundo 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 las estructuras de datos persistentes , que son bastante interesantes.
Invierta 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;
}
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;
}
Modifique el recorrido de prepedido para voltear los nodos antes de seguir avanzando.
#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)
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
Puedes 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);
}
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();
}
}