Suma de los Nodes de la imagen especular de un árbol binario completo en orden

Dado un árbol binario completo, la tarea es encontrar la suma de los Nodes de la imagen espejo en orden, es decir, encontrar el recorrido en orden del subárbol izquierdo y para cada Node atravesado, sume el valor de su Node espejo al valor del Node actual. .

Ejemplos: 

Aporte: 
 

Salida: 
20 
51 
19 
10 
El recorrido en orden del subárbol izquierdo del árbol dado es 4 23 11 5. 
Agregando los Nodes espejo, 
4 + 16 = 20 
23 + 28 = 51 
11 + 8 = 19 
5 + 5 = 10 
 

Enfoque: Usaremos 2 punteros para mantener 2 Nodes que son la imagen especular entre sí. Entonces, tomemos root1 y root2 como 2 Nodes de imagen especular. Ahora, el hijo izquierdo de root1 y el hijo derecho de root2 serán la imagen especular entre sí. Pasaremos estos dos Nodes (root1->left y root2->right) para la próxima llamada recursiva. Dado que tenemos que atravesar en orden, una vez que se atraviesa el subárbol izquierdo, imprimimos los datos raíz actuales y luego cruzamos el subárbol derecho. De manera similar, para el subárbol derecho, el hijo derecho de root1 y el hijo izquierdo de root2 serán la imagen especular entre sí. Pasaremos estos dos Nodes (root1->right y root2->left) para la próxima llamada recursiva.

A continuación se muestra la implementación del enfoque anterior. 

// C++ implementation of the approach
#include <iostream>
using namespace std;
typedef struct node {
 
    // struct to store data and links to
    // its left and right child
    int data;
    struct node* l;
    struct node* r;
    node(int d)
    {
 
        // Initialize data for the current node
        // with the passed value as d
        data = d;
 
        // Initialize left child to NULL
        l = NULL;
 
        // Initialize right child to NULL
        r = NULL;
    }
} Node;
 
// Function to print the required inorder traversal
void printInorder(Node* rootL, Node* rootR)
{
    // We are using 2 pointers for the nodes
    // which are mirror image of each other
    // If both child are NULL return
    if (rootL->l == NULL && rootR->r == NULL)
        return;
 
    // Since inorder traversal is required
    // First left, then root and then right
    printInorder(rootL->l, rootR->r);
    cout << rootL->l->data + rootR->r->data << endl;
    printInorder(rootL->r, rootR->l);
}
 
// Driver code
int main()
{
    Node* root = new Node(5);
    root->l = new Node(23);
    root->r = new Node(28);
    root->l->l = new Node(4);
    root->l->r = new Node(11);
    root->r->l = new Node(8);
    root->r->r = new Node(16);
 
    printInorder(root, root);
 
    // Since root is mirror image of itself
    if (root)
        cout << root->data * 2 << endl;
 
    return 0;
}

// Java implementation of the approach
import java.util.*;
 
class GFG
{
    static class Node
    {
 
        // struct to store data and links to
        // its left and right child
        int data;
        Node l;
        Node r;
        Node(int d)
        {
     
            // Initialize data for the current Node
            // with the passed value as d
            data = d;
     
            // Initialize left child to null
            l = null;
     
            // Initialize right child to null
            r = null;
        }
    }
 
    // Function to print the required inorder traversal
    static void printInorder(Node rootL, Node rootR)
    {
        // We are using 2 pointers for the Nodes
        // which are mirror image of each other
        // If both child are null return
        if (rootL.l == null && rootR.r == null)
            return;
     
        // Since inorder traversal is required
        // First left, then root and then right
        printInorder(rootL.l, rootR.r);
        System.out.println(rootL.l.data + rootR.r.data );
        printInorder(rootL.r, rootR.l);
    }
 
    // Driver code
    public static void main(String args[])
    {
        Node root = new Node(5);
        root.l = new Node(23);
        root.r = new Node(28);
        root.l.l = new Node(4);
        root.l.r = new Node(11);
        root.r.l = new Node(8);
        root.r.r = new Node(16);
     
        printInorder(root, root);
     
        // Since root is mirror image of itself
        if (root != null)
            System.out.println(root.data * 2 );
     
    }
}
 
// This code is contributed by Arnab Kundu

# Python3 implementation of the approach
 
class Node:
     
    def __init__(self, d):
        self.data = d
        self.l = None
        self.r = None
 
# Function to print the required inorder traversal
def printInorder(rootL, rootR):
  
    # We are using 2 pointers for the nodes
    # which are mirror image of each other
    # If both child are None return
    if rootL.l == None and rootR.r == None:
        return
 
    # Since inorder traversal is required
    # First left, then root and then right
    printInorder(rootL.l, rootR.r)
    print(rootL.l.data + rootR.r.data)
    printInorder(rootL.r, rootR.l)
  
# Driver code
if __name__ == "__main__":
  
    root = Node(5)
    root.l = Node(23)
    root.r = Node(28)
    root.l.l = Node(4)
    root.l.r = Node(11)
    root.r.l = Node(8)
    root.r.r = Node(16)
 
    printInorder(root, root)
 
    # Since root is mirror image of itself
    if root:
        print(root.data * 2)
 
# This code is contributed by Rituraj Jain

// C# implementation of the approach
using System;
 
class GFG
{
    public class Node
    {
 
        // struct to store data and links to
        // its left and right child
        public int data;
        public Node l;
        public Node r;
        public Node(int d)
        {
     
            // Initialize data for the current Node
            // with the passed value as d
            data = d;
     
            // Initialize left child to null
            l = null;
     
            // Initialize right child to null
            r = null;
        }
    }
 
    // Function to print the required inorder traversal
    static void printInorder(Node rootL, Node rootR)
    {
        // We are using 2 pointers for the Nodes
        // which are mirror image of each other
        // If both child are null return
        if (rootL.l == null && rootR.r == null)
            return;
     
        // Since inorder traversal is required
        // First left, then root and then right
        printInorder(rootL.l, rootR.r);
        Console.WriteLine(rootL.l.data + rootR.r.data );
        printInorder(rootL.r, rootR.l);
    }
 
    // Driver code
    public static void Main(String []args)
    {
        Node root = new Node(5);
        root.l = new Node(23);
        root.r = new Node(28);
        root.l.l = new Node(4);
        root.l.r = new Node(11);
        root.r.l = new Node(8);
        root.r.r = new Node(16);
     
        printInorder(root, root);
     
        // Since root is mirror image of itself
        if (root != null)
            Console.WriteLine(root.data * 2 );
     
    }
}
 
// This code is contributed by Arnab Kundu

<script>
 
// Javascript implementation of the approach
class Node
{
    constructor(d)
    {
        this.l = null;
        this.r = null;
        this.data = d;
    }
}
 
// Function to print the required inorder traversal
function printInorder(rootL, rootR)
{
     
    // We are using 2 pointers for the Nodes
    // which are mirror image of each other
    // If both child are null return
    if (rootL.l == null && rootR.r == null)
        return;
   
    // Since inorder traversal is required
    // First left, then root and then right
    printInorder(rootL.l, rootR.r);
    document.write(rootL.l.data +
                   rootR.r.data + "</br>");
    printInorder(rootL.r, rootR.l);
}
 
// Driver code
let root = new Node(5);
root.l = new Node(23);
root.r = new Node(28);
root.l.l = new Node(4);
root.l.r = new Node(11);
root.r.l = new Node(8);
root.r.r = new Node(16);
 
printInorder(root, root);
 
// Since root is mirror image of itself
if (root != null)
    document.write(root.data * 2 );
 
// This code is contributed by suresh07
 
</script>

20
51
19
10

Complejidad temporal: O(N)
Espacio auxiliar: O(N)