C++でのZigZagツリートラバーサル

この問題では、二分木が与えられます。私たちの仕事は、二分木をジグザグ形式で印刷することです。

問題を理解するために例を見てみましょう

上記の二分木のジグザグ走査は

3    5    1    8    7    0    4

この問題を解決するには、二分木をレベルごとにトラバースする必要があります。トラバーサルの順序は、各レベルの後で反転します。

ここで、2つのスタック（現在と次）と1つの値を注文に使用します。まず、ノードを現在のノードからトラバースし、ノードを左の子から右の子にフィードして、逆の順序が返されるようにします。再び現在から逆になります。順序変数は、どちらの面を印刷するかを示す上で重要な役割を果たします。

例

ソリューションの実装を示すプログラム

#include <iostream>
#include <stack>
using namespace std;
struct Node {
   int data;
   struct Node *left, *right;
};
void zigZagTreeTraversal(struct Node* root){
   if (!root)
      return;
   stack<struct Node*> currentlevel;
   stack<struct Node*> nextlevel;
   currentlevel.push(root);
   bool LtR = true;
   while (!currentlevel.empty()) {
      struct Node* temp = currentlevel.top();
      currentlevel.pop();
      if (temp) {
         cout<<temp->data<<"\t";
         if (LtR) {
            if (temp->left)
               nextlevel.push(temp->left);
            if (temp->right)
               nextlevel.push(temp->right);
         }
         else {
            if (temp->right)
               nextlevel.push(temp->right);
            if (temp->left)
               nextlevel.push(temp->left);
         }
      }
      if (currentlevel.empty()) {
         LtR = !LtR;
         swap(currentlevel, nextlevel);
      }
   }
}
struct Node* insertNode(int data){
   struct Node* node = new struct Node;
   node->data = data;
   node->left = node->right = NULL;
   return (node);
}
int main() {
   struct Node* root = insertNode(3);
   root->left = insertNode(1);
   root->right = insertNode(5);
   root->left->left = insertNode(8);
   root->left->right = insertNode(7);
   root->right->left = insertNode(0);
   root->right->right = insertNode(4);
   cout << "ZigZag traversal of the given binary tree is \n";
   zigZagTreeTraversal(root);
   return 0;
}

出力

ZigZag traversal of the given binary tree is
3    5    1    8    7    0    4