Спираль формасындагы деңгээлдеги буйрук  


Кыйынчылык деңгээли орто
Көп суралган Adobe Amazon алма Bloomberg Flipkart Microsoft Qualtrics ServiceNow
Биринчи издөө чөмөлө дарак

Бул көйгөйдө биз а экилик дарак, спираль түрүндө анын деңгээлинин өтүшүн басып чыгарыңыз.

мисалы,  

кирүү

Спираль формасындагы деңгээлдеги буйрук
продукция
10 30 20 40 50 80 70 60

Спираль түрүндө деңгээлди өтүүнүн жөнөкөй ыкмасы  

Идея кезекти колдонуп, кадимки деңгээлдеги буйрукту өтүү жана стекти колдонуп, керектүү деңгээлдерди тескери тартипте басып чыгаруу.

1-деңгээл артка кайтарылбайт, 2-деңгээл артка кайтарылат, 3-деңгээл артка кайтарылбайт ж.б. Тескери басылып чыгышы керек болгон бардык деңгээлдер үчүн, ошол деңгээлдеги бардык элементтерди стекке кошуп, андан кийин басып чыгарыңыз.

  1. Кезек түзүп, ага тамырын түртүп коюңуз. Буль өзгөрмөсүн тескерисинче жалган деп баштаңыз.
  2. Кезек бош болбосо дагы, кадамдарды кайталаңыз
  3. Кезектин өлчөмү катары өзгөрүлмө өлчөмдү баштаңыз. Циклди 1ден чоңдукка чейин иштетип, ар бир кайталоодо элементти кезектен алып салыңыз жана эгерде тескериси чын болсо, аны стекке түртүп бериңиз, болбосо басып чыгарыңыз. Ошондой эле, алынып салынган элементтердин балдарын кезекке түртүп салыңыз.
  4. Эгер тескерисинче туура болсо, стектин элементтерин басып чыгарыңыз.
  5. Негат арткы, башкача айтканда, эгерде тескери туура болсо, анда аны жалган кыл, ал эми эгерде тескери болсо, анда аны чын кыл.

JAVA коду

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 ++ коду

#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

Спираль түрүндө деңгээлдин өтүшү үчүн татаалдыкты талдоо

Убакыт татаалдыгы = O (n), убакыттын татаалдыгынын жогорку чеги (4 * n)
Космостун татаалдыгы = O (N)

ошондой эле
Биринчи жаман версия

Спираль түрүндө деңгээлди өткөрүү боюнча оптималдуу ыкма  

Деңгээлдин өтүшүн басып чыгаруу үчүн эки стекти колдонобуз. Аларды тиешелүүлүгүнө жараша st1 жана st2 деп атайбыз.
st1 кадимки деңгээлдин өтүшүн басып чыгарат жана st2 тескери деңгээлдин өтүүсүн басып чыгарат.

  1. Тамырды st1 түртүп салыңыз.
  2. St1 же st2 бош болбосо дагы, төмөнкүнү аткарыңыз,
    1. St1 бош болбосо дагы, бир элементти чыгарып, басып чыгарыңыз жана анын сол жана оң балдарын st2 түртүп салыңыз.
    2. St2 бош болбосо дагы, бир элементти чыгарып, басып чыгарыңыз жана анын оң жана сол балдарын st1 түртүп, тескери тартибине көңүл буруңуз, башкача айтканда, алгач оң баланы, андан кийин сол баланы түртүп алыңыз.

JAVA коду

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 ++ коду

#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

Спираль түрүндө деңгээлдин өтүшү үчүн татаалдыкты талдоо

Убакыт татаалдыгы = O (N), убакыттын татаалдыгынын жогорку чеги (2 * n)
Космостун татаалдыгы = O (N)

ошондой эле
Эң кыска Палиндром

шилтемелер