Абход узроўню ў спіральнай форме  


Узровень складанасці серада
Часта пытаюцца ў Саман амазонка яблык Bloomberg Flipkart Microsoft Qualtrics ServiceNow
Шырыня Першы пошук Стэк дрэва

У гэтай праблеме мы далі бінарнае дрэва, раздрукуйце абход яго ўзроўню ў спіральнай форме.

Прыкладаў  

уваход

Абход узроўню ў спіральнай формеPin
выхад
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 (п), верхняя мяжа часовай складанасці (4 * п)
Складанасць прасторы = Аб (п)

Глядзіце таксама
Самы кароткі паліндром

Аптымальны падыход для абходу ўзроўню ў спіральнай форме  

Мы выкарыстоўваем два стэкі для друку абходу ўзроўню. Назавем іх адпаведна 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

Аналіз складанасці для абходу парадку ўзроўню ў спіральнай форме

Складанасць часу = Аб (п), верхняя мяжа часовай складанасці (2 * n)
Складанасць прасторы = Аб (п)

Глядзіце таксама
Заменіце элементы на найвялікшы элемент у правым баку рашэння Leetcode

Спасылкі