Aplanar árbol binario en orden de recorrido Zig Zag

Dado un árbol binario, la tarea es aplanarlo en orden de recorrido en zigzag del árbol. En el árbol binario aplanado, el Node izquierdo de todos los Nodes debe ser NULL.
Ejemplos: 
 

Input: 
          1 
        /   \ 
       5     2 
      / \   / \ 
     6   4 9   3 
Output: 1 2 5 6 4 9 3

Input:
      1
       \
        2
         \
          3
           \
            4
             \
              5
Output: 1 2 3 4 5

Enfoque: Resolveremos este problema simulando el recorrido ZigZag de Binary Tree. 
Algoritmo: 
 

1. Cree dos pilas, «c_lev» y «n_lev» y almacene los Nodes del árbol binario actual y del siguiente nivel.
2. Cree una variable «anterior» e inicialícela por Node principal.
3. Empuje los hijos derecho e izquierdo del padre en la pila c_lev.
4. Aplicar ZigZag transversal. Digamos que «curr» es el elemento más alto en «c_lev». Después, 
   • Si ‘curr’ es NULL, continúe.
   • De lo contrario, presione curr->left y curr->right en la pila «n_lev» en el orden apropiado. Si estamos realizando un recorrido de izquierda a derecha, entonces curr->left se presiona primero; de lo contrario, curr->right se presiona primero.
   • Establecer anterior = actual.

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

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Node of the binary tree
struct node {
    int data;
    node* left;
    node* right;
    node(int data)
    {
        this->data = data;
        left = NULL;
        right = NULL;
    }
};
 
// Function to flatten Binary tree
void flatten(node* parent)
{
    // Queue to store node
    // for BFS
    stack<node *> c_lev, n_lev;
 
    c_lev.push(parent->left);
    c_lev.push(parent->right);
 
    bool lev = 1;
    node* prev = parent;
 
    // Code for BFS
    while (c_lev.size()) {
 
        // Size of queue
        while (c_lev.size()) {
 
            // Front most node in
            // queue
            node* curr = c_lev.top();
            c_lev.pop();
 
            // Base case
            if (curr == NULL)
                continue;
            prev->right = curr;
            prev->left = NULL;
            prev = curr;
 
            // Pushing new elements
            // in queue
            if (!lev)
                n_lev.push(curr->left);
            n_lev.push(curr->right);
            if (lev)
                n_lev.push(curr->left);
        }
        lev = (!lev);
        c_lev = n_lev;
        while (n_lev.size())
            n_lev.pop();
    }
 
    prev->left = NULL;
    prev->right = NULL;
}
 
// Function to print flattened
// binary tree
void print(node* parent)
{
    node* curr = parent;
    while (curr != NULL)
        cout << curr->data << " ", curr = curr->right;
}
 
// Driver code
int main()
{
    node* root = new node(1);
    root->left = new node(5);
    root->right = new node(2);
    root->left->left = new node(6);
    root->left->right = new node(4);
    root->right->left = new node(9);
    root->right->right = new node(3);
 
    // Calling required functions
    flatten(root);
 
    print(root);
 
    return 0;
}

<script>
 
// Javascript implementation of the approach
 
// Node of the binary tree
class node {
 
    constructor(data)
    {
        this.data = data;
        this.left = null;
        this.right = null;
    }
};
 
// Function to flatten Binary tree
function flatten()
{
    // Queue to store node
    // for BFS
    var c_lev = [], n_lev = [];
 
    c_lev.push(parent.left);
    c_lev.push(parent.right);
 
    var lev = 1;
    var prev = parent;
 
    // Code for BFS
    while (c_lev.length!=0) {
 
        // Size of queue
        while (c_lev.length!=0) {
 
            // Front most node in
            // queue
            var curr = c_lev[c_lev.length-1];
            c_lev.pop();
 
            // Base case
            if (curr == null)
                continue;
 
            prev.right = curr;
            prev.left = null;
            prev = curr;
 
            // Pushing new elements
            // in queue
            if (!lev)
                n_lev.push(curr.left);
            n_lev.push(curr.right);
            if (lev)
                n_lev.push(curr.left);
        }
 
        lev = lev==0?1:0;
        c_lev = n_lev;
        n_lev = [];
    }
 
    prev.left = null;
    prev.right = null;
}
 
// Function to print flattened
// binary tree
function print()
{
    var curr = parent;
    while (curr != null)
    {
        document.write(curr.data + " ");
        curr = curr.right;
    }     
}
 
// Driver code
var parent = new node(1);
parent.left = new node(5);
parent.right = new node(2);
parent.left.left = new node(6);
parent.left.right = new node(4);
parent.right.left = new node(9);
parent.right.right = new node(3);
// Calling required functions
flatten();
print();
 
// This code is contributed by rrrtnx.
</script>

1 2 5 6 4 9 3

Complejidad de tiempo: O(N) 
Complejidad de espacio: O(N) donde N es el tamaño del árbol binario.