나선형 형태의 레벨 순서 순회

난이도 중급
자주 묻는 질문 어도비 벽돌 아마존 Apple 블룸버그 게시물에서 Flipkart Microsoft Qualtrics ServiceNow
폭 우선 검색 스택 나무조회수 41

이 문제에서 우리는 이진 트리, 레벨 순서 순회를 나선형 형태로 인쇄합니다.

입력

나선형 형태의 레벨 순서 순회
산출
10 30 20 40 50 80 70 60

나선형 형태의 레벨 순서 순회에 대한 순진한 접근 방식

아이디어는 큐를 사용하여 일반 레벨 순서 순회를 수행하고 스택을 사용하여 필요한 레벨을 역순으로 인쇄하는 것입니다.

레벨 1은 반전되지 않고 레벨 2는 반전되며 레벨 3은 반전되지 않습니다. 역순으로 인쇄 할 모든 레벨에 대해 해당 레벨의 모든 요소를 ​​스택에 추가 한 다음 인쇄합니다.

  1. 큐를 만들고 루트를 푸시합니다. 부울 변수를 false로 초기화합니다.
  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

나선형 형태의 레벨 오더 순회에 대한 복잡성 분석

시간 복잡성 = 의 위에), 시간 복잡도의 상한은 (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)

참조

Translate »