ZigZag Tree Traversal ใน C++

ในปัญหานี้ เราได้รับไบนารีทรี งานของเราคือพิมพ์ไบนารีทรีในรูปแบบซิกแซก

มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน

การข้ามซิกแซกของไบนารีทรีด้านบนคือ

3    5    1    8    7    0    4

เพื่อแก้ปัญหานี้ เราจำเป็นต้องสำรวจระดับไบนารีทรีทีละระดับ ลำดับการข้ามผ่านจะพลิกกลับหลังแต่ละระดับ

ตอนนี้ เราจะใช้สองกอง (ปัจจุบันและถัดไป) และหนึ่งค่าสำหรับการสั่งซื้อ ขั้นแรก เราจะสำรวจโหนดจากโหนดปัจจุบันและโหนดฟีดจากโหนดย่อยด้านซ้ายไปยังโหนดย่อยที่ถูกต้อง เพื่อที่จะส่งคืนลำดับย้อนกลับ ย้อนกลับจากปัจจุบันอีกครั้ง ตัวแปรลำดับมีบทบาทสำคัญในการแสดงด้านที่จะพิมพ์

ตัวอย่าง

โปรแกรมแสดงการใช้งานโซลูชันของเรา

#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