Bu problemdə bir ikili ağac, səviyyə sifarişini spiral şəklində çap edin.
Mündəricat
Nümunələr
Input
Buraxılış
10 30 20 40 50 80 70 60
Spiral formada səviyyə sifarişinin keçməsi üçün sadəlövh yanaşma
Fikir, bir sıra istifadə edərək normal səviyyəli sifariş keçidini etmək və lazımi səviyyələri tərs qaydada çap etmək üçün bir yığın istifadə etməkdir.
Səviyyə 1 tərs çevrilmir, səviyyə 2 tərs, səviyyə 3 geri çevrilmir və s. Ters qaydada yazdırılmalı olan bütün səviyyələr üçün bu səviyyə bütün elementlərini bir yığına əlavə edin və sonra çap edin.
- Bir növbə yaradın və kökü ona itələyin. Boole dəyişənini tərs olaraq yalan olaraq başlatın.
- Növbə boş olmasa da, addımları təkrarlayın
- Dəyişən ölçünü növbənin ölçüsü kimi başladın. 1-dən ölçüyə qədər bir döngə işlədin və hər təkrarlanmada bir elementi növbədən çıxarın və əksi doğrudursa, onu yığına itələyin, əksinə çap edin. Ayrıca, silinmiş elementlərin uşaqlarını növbəyə itələyin.
- Tersi doğrudursa, yığının elementlərini yazdırın.
- Ters bax, yəni tersi doğrudursa, yalan et, tersi yalnışsa, onu deqiq et.
JAVA Kodu
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
public class Naive {
// class representing a tree node
static class Node {
int data;
Node left, right;
public Node(int data) {
this.data = data;
}
}
private static void spiralOrderTraversal(Node root) {
if (root == null) {
return;
}
// create a queue for level order traversal
Queue<Node> queue = new LinkedList<>();
// create a stack (used to print a level in reverse order)
Stack<Node> stack = new Stack<>();
// Initially reverse is false
boolean reverse = false;
// add the root to the queue
queue.add(root);
// Do a normal level order traversal
while (!queue.isEmpty()) {
int size = queue.size();
// Traverse current level
for (int i = 0; i < size; i++) {
Node curr = queue.poll();
// if reverse is true, push the element to stack, else print it
if (reverse) {
stack.push(curr);
} else {
System.out.print(curr.data + " ");
}
if (curr.left != null) {
queue.add(curr.left);
}
if (curr.right != null) {
queue.add(curr.right);
}
}
// if this level has to be reversed, print the content of the stack
if (reverse) {
while (!stack.isEmpty()) {
System.out.print(stack.pop().data + " ");
}
}
// negate reverse
reverse = !reverse;
}
}
public static void main(String[] args) {
// Example tree
Node root = new Node(10);
root.left = new Node(20);
root.right = new Node(30);
root.right.left = new Node(40);
root.right.right = new Node(50);
root.right.left.left = new Node(60);
root.right.right.left = new Node(70);
root.right.right.right = new Node(80);
spiralOrderTraversal(root);
}
}
10 30 20 40 50 80 70 60
C ++ kodu
#include<bits/stdc++.h>
using namespace std;
// class representing a tree node
class Node {
public:
int data;
Node *left;
Node *right;
Node(int d) {
data = d;
left = right = NULL;
}
};
// function to create a new node
Node* newNode(int x) {
Node *node = new Node(x);
return node;
}
void spiralOrderTraversal(Node *root) {
if (root == NULL) {
return;
}
// create a queue for level order traversal
queue<Node*> q;
// create a stack (used to print a level in reverse order)
stack<Node*> st;
// Initially reverse is false
bool reverse = false;
// add the root to the queue
q.push(root);
// Do a normal level order traversal
while (!q.empty()) {
int size = q.size();
// Traverse current level
for (int i = 0; i < size; i++) {
Node* curr = q.front();
q.pop();
// if reverse is true, push the element to stack, else print it
if (reverse) {
st.push(curr);
} else {
cout<<curr->data<<" ";
}
if (curr->left != NULL) {
q.push(curr->left);
}
if (curr->right != NULL) {
q.push(curr->right);
}
}
// if this level has to be reversed, print the content of the stack
if (reverse) {
while (!st.empty()) {
cout<<st.top()->data<<" ";
st.pop();
}
}
// negate reverse
reverse = !reverse;
}
}
int main() {
// Example Tree
Node *root = newNode(10);
root->left = newNode(20);
root->right = newNode(30);
root->right->left = newNode(40);
root->right->right = newNode(50);
root->right->left->left = newNode(60);
root->right->right->left = newNode(70);
root->right->right->right = newNode(80);
spiralOrderTraversal(root);
}
10 30 20 40 50 80 70 60
Spiral formada səviyyə sifarişinin keçməsi üçün komplekslik analizi
Zaman Mürəkkəbliyi = O (n), zaman mürəkkəbliyinin yuxarı həddi (4 * n)
Kosmik Mürəkkəblik = O (n)
Spiral formada səviyyə sifarişinin keçməsi üçün optimal yanaşma
Səviyyə sifariş keçidini çap etmək üçün iki yığından istifadə edirik. Onları sırasıyla st1 və st2 adlandıraq.
st1 adi səviyyə keçidini və st2 tərs səviyyə sifarişini çap edir.
- Kökü st1-də itələyin.
- St1 və ya st2 boş olmadıqda aşağıdakıları edin,
- St1 boş olmasa da, bir elementi açın və yazdırın və sol və sağ uşaqlarını st2-yə itələyin.
- St2 boş olmasa da, bir elementi açın və yazdırın və sağ və sol uşaqlarını st1-ə itələyin, tərs sıraya diqqət yetirin, yəni əvvəlcə sağ uşağı və sonra sol uşağı itələyin.
JAVA Kodu
import java.util.Stack;
public class LevelOrderTraversalInSpiralForm {
// class representing a tree node
static class Node {
int data;
Node left, right;
public Node(int data) {
this.data = data;
}
}
private static void spiralOrderTraversal(Node root) {
if (root == null) {
return;
}
// Create two stacks
Stack<Node> st1 = new Stack<>();
Stack<Node> st2 = new Stack<>();
// push the root to st1
st1.push(root);
// do the following while either st1 is not empty or st2 is not empty
while (!st1.isEmpty() || !st2.isEmpty()) {
// while st1 is not empty
while (!st1.isEmpty()) {
// pop the current element and print it
Node curr = st1.pop();
System.out.print(curr.data + " ");
// push its children to st2
if (curr.left != null)
st2.push(curr.left);
if (curr.right != null)
st2.push(curr.right);
}
// while st2 is not empty
while (!st2.isEmpty()) {
// pop the current element and print it
Node curr = st2.pop();
System.out.print(curr.data + " ");
// Push its right child and left child to st1 respectively
if (curr.right != null)
st1.push(curr.right);
if (curr.left != null)
st1.push(curr.left);
}
}
System.out.println();
}
public static void main(String[] args) {
// Example tree
Node root = new Node(10);
root.left = new Node(20);
root.right = new Node(30);
root.right.left = new Node(40);
root.right.right = new Node(50);
root.right.left.left = new Node(60);
root.right.right.left = new Node(70);
root.right.right.right = new Node(80);
spiralOrderTraversal(root);
}
}
10 30 20 40 50 80 70 60
C ++ kodu
#include<bits/stdc++.h>
using namespace std;
// class representing a tree node
class Node {
public:
int data;
Node *left;
Node *right;
Node(int d) {
data = d;
left = right = NULL;
}
};
// function to create a new node
Node* newNode(int x) {
Node *node = new Node(x);
return node;
}
void spiralOrderTraversal(Node *root) {
if (root == NULL) {
return;
}
// Create two stacks
stack<Node*> st1;
stack<Node*> st2;
// push the root to st1
st1.push(root);
// do the following while either st1 is not empty or st2 is not empty
while (!st1.empty() || !st2.empty()) {
// while st1 is not empty
while (!st1.empty()) {
// pop the current element and print it
Node *curr = st1.top();
st1.pop();
cout<<curr->data<<" ";
// push its children to st2
if (curr->left != NULL)
st2.push(curr->left);
if (curr->right != NULL)
st2.push(curr->right);
}
// while st2 is not empty
while (!st2.empty()) {
// pop the current element and print it
Node *curr = st2.top();
st2.pop();
cout<<curr->data<<" ";
// Push its right child and left child to st1 respectively
if (curr->right != NULL)
st1.push(curr->right);
if (curr->left != NULL)
st1.push(curr->left);
}
}
cout<<endl;
}
int main() {
// Example Tree
Node *root = newNode(10);
root->left = newNode(20);
root->right = newNode(30);
root->right->left = newNode(40);
root->right->right = newNode(50);
root->right->left->left = newNode(60);
root->right->right->left = newNode(70);
root->right->right->right = newNode(80);
spiralOrderTraversal(root);
}
10 30 20 40 50 80 70 60
Spiral formada səviyyə sifarişinin keçməsi üçün komplekslik analizi
Zaman Mürəkkəbliyi = O (n)zaman mürəkkəbliyinin yuxarı həddi (2 * n)
Kosmik Mürəkkəblik = O (n)
