바이너리 트리 지그재그 레벨 순서 순회


난이도 중급
자주 묻는 질문 어도비 벽돌 아마존 Apple 블룸버그 이베이 Flipkart Microsoft Qualtrics ServiceNow
이진 트리 폭 우선 검색 스택 나무 트리 순회

주어진 이진 트리, 인쇄 지그재그 레벨 순서 노드 값의 순회. (즉, 왼쪽에서 오른쪽으로, 다음 레벨을 위해 오른쪽에서 왼쪽으로 번갈아 가며).

아래 주어진 이진 트리를 고려하십시오

바이너리 트리 지그재그 레벨 순서 순회

아래는 위 이진 트리의 지그재그 수준 순서 순회입니다.

바이너리 트리 지그재그 레벨 순서 순회

이진 트리 지그재그 수준 순서 순회를위한 솔루션 유형

  1. Breadth First 검색 및 두 스택 사용
  2. Depth First 검색 및지도 사용

BFS 및 두 스택

이진 트리 지그재그 수준 순서 순회에 대한 접근 방식

우리는 수행합니다 BFS 나무에 두 개의 스택을 사용합니다. 현재다음 것. 현재 모든 노드를 현재 순서대로 레벨 (왼쪽에서 오른쪽 또는 오른쪽에서 왼쪽). 다음 것 다음 레벨의 모든 노드를 반대 순서로 저장합니다. 흐름. 현재 레벨의 모든 요소를 ​​처리 한 후 현재 비어있게되면 저장된 노드를 다음 것 으로 현재 다음 단계로 이동합니다. 이제 다음 레벨 노드가 다시 저장됩니다. 다음 것. 이 과정은 현재다음 것 스택이 비어 있지 않습니다.

암호알고리즘

  1. 두 개의 스택 생성 현재다음.
  2. 부울 변수 만들기 왼쪽 아니면 오른쪽, 왼쪽에서 오른쪽으로 모드에서 오른쪽에서 왼쪽으로 모드로 전환하는 데 사용됩니다.
  3. 현재에 루트를 삽입하고 BFS 순회를 시작합니다.
  4. BFS 순회 :
    1. 현재 스택에서 노드를 꺼내 해당 값을 인쇄합니다.
    2. 사용하여 모드 확인 왼쪽 아니면 오른쪽.
    3. 모드가 왼쪽에서 오른쪽 인 경우 (예 : 왼쪽 아니면 오른쪽 = true), 현재 노드의 자식 (왼쪽 앞 오른쪽)을 다음 것 스택.
    4. 모드가 오른쪽에서 왼쪽이면 (즉 왼쪽 아니면 오른쪽 = false), 현재 노드의 자식 (왼쪽 앞 오른쪽)을 다음 것 스택.
    5. 현재 레벨의 모든 노드를 처리 한 후 현재 스택이 비워지면 다음 레벨로 이동합니다. 의 모든 노드를 비 웁니다. 다음 것흐름.
    6. 이제부터 노드의 모든 자식은 현재 에 저장됩니다 다음.
  5. 4.1-4.6 단계를 수행하여 현재다음 것 스택이 비어 있지 않습니다.

 

바이너리 트리 지그재그 레벨 순서 순회

바이너리 트리 지그재그 레벨 순서 순회

실시

C ++ 프로그램
#include <iostream>
#include <bits/stdc++.h>
using namespace std;

// blueprint of the tree node
class Node
{
    public : 
    int data;
    Node *left, *right, *next;
    
    Node(int key)
    {
        data = key;
        left = right = next = NULL;
    }
};

/* function that performs zigzag Traversal
    in similar manner to BFS */
void zigzagTraversal(Node *root)
{
    /*check if the tree is empty*/
    if(root == NULL)
    return;
    
    /*create two stacks*/
    /*current stores the current level order Traversal,
    next stores the next level order traversal      */
    stack<Node*> current;
    stack<Node*> next;
    
    /*start with root*/
    current.push(root);
    
    /*leftOrRight is to check whether to traverse from right or left*/
    /*Change it after every traversing every level*/
    bool leftOrRight = true;
    
    while(!current.empty())
    {
        Node *curr = current.top();
        current.pop();
        
        if(curr != NULL)
        {
            cout<<curr->data<<" ";
            
            /* if next level has to be traversed left to right*/
            if(leftOrRight)
            {
                if(curr->left)
                next.push(curr->left);
                
                if(curr->right)
                next.push(curr->right);
            }
            
            /* if next level has to be traversed right to left*/
            else
            {
                if(curr->right)
                next.push(curr->right);
                
                if(curr->left)
                next.push(curr->left);
            }
            
            /*if the current level has been completely 
            traversed and we have to move on to next level*/
            if(current.empty())
            {
                swap(current,next);
                leftOrRight = !leftOrRight;
            }
        }
    }
}

// function to simply perform inorder traversal of the tree
void inorder(Node *root)
{
    if(root == NULL)
    return;
    
    inorder(root->left);
    cout<<root->data<<" ";
    inorder(root->right);
}

int main()
{
    /*create the Binary Tree*/
    Node *root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    root->right->right = new Node(6);
    root->left->left->left = new Node(7);
    root->right->right->right = new Node(8);
    
    zigzagTraversal(root);
    
    return 0;
}
1 3 2 4 5 6 8 7
자바 프로그램
import java.util.*;
import java.io.*;

class tutorialCup
{
    // blueprint of the tree node
    static class Node
    {
        int data;
        Node left, right, next;
        
        Node(int key)
        {
            data = key;
            left = right = next = null;
        }
    }

    /* function that performs zigzag Traversal
    in similar manner to BFS */
    static void zigzagTraversal(Node root)
    {
        /*check if the tree is empty*/
        if(root == null)
        return;
        
        /*create two stacks*/
        /*current stores the current level order Traversal,
        next stores the next level order traversal      */
        Stack <Node> current = new Stack<>();
        Stack <Node> next = new Stack<>();
        
        /*start with root*/
        current.push(root);
        
        /*leftOrRight is to check whether to traverse from right or left*/
        /*Change it after every traversing every level*/
        boolean leftOrRight = true;
        
        while(!current.isEmpty())
        {
            Node curr = current.pop();
            
            if(curr != null)
            {
                System.out.print(curr.data+" ");
                
                /* if next level has to be traversed left to right*/
                if(leftOrRight)
                {
                    if(curr.left != null)
                    next.push(curr.left);
                    
                    if(curr.right != null)
                    next.push(curr.right);
                }
                
                /* if next level has to be traversed right to left*/
                else
                {
                    if(curr.right != null)
                    next.push(curr.right);
                    
                    if(curr.left != null)
                    next.push(curr.left);
                }
                
                /*if the current level has been completely 
                traversed and we have to move on to next level*/
                if(current.isEmpty())
                {
                    Stack <Node> temp = current;
                    current = next;
                    next = temp;
                    
                    leftOrRight = !leftOrRight;
                }
            }
        }
    }
    
    // function to simply perform inorder traversal of the tree
    static void inorder(Node root)
    {
        if(root == null)
        return;
        
        inorder(root.left);
        System.out.print(root.data+" ");
        inorder(root.right);
    }
    
    public static void main (String[] args) 
    {
        /*create the Binary Tree*/
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);
        root.right.right = new Node(6);
        root.left.left.left = new Node(7);
        root.right.right.right = new Node(8);
        
        zigzagTraversal(root);
    }
}
1 3 2 4 5 6 8 7

이진 트리 지그재그 수준 순서 순회에 대한 복잡성 분석

  1. 시간 복잡도 : T (n) = O (n)
  2. 공간 복잡성 : T (n) = O (2n) = O (n), 두 개의 스택이 사용됩니다.

DFS 및지도

이진 트리 지그재그 수준 순서 순회에 대한 접근 방식

Hashmap 데이터 구조를 사용합니다. 이 Hashmap은 트리의 수준 (정수 값)을 동적 배열 (해당 특정 수준의 모든 노드 포함)에 매핑합니다. 지도를 사용하여 inorder traversal을 수행 할 때 필요한 매핑을 얻습니다. 연속 레벨이 반대 순서로 인쇄되도록해야합니다.

얻은 매핑은 다음과 같습니다.

(레벨-> 동적 어레이 {해당 레벨의 노드 포함})

암호알고리즘

  1. Hashmap 변수 만들기 메모.
  2. 다음을 사용하여 inorder traversal을 수행합니다. 메모 트리의 각 노드 수준을 추적합니다.
  3. 특정 수준 (키-값)이지도에없는 경우 해당 수준 (키)을지도에 삽입하고 빈 동적에 매핑합니다. 정렬 (매핑 된 값).
  4. 순회 중에 발견 된 노드를 벡터 (해당 노드의 수준에 해당하는 동적 배열)에 삽입합니다.
  5. 순회가 완료된 후 이전 레벨의 인쇄 순서와 반대 순서로 인접한 레벨을 각각 인쇄합니다. (각 레벨은 트리 노드를 포함하는 동적 배열입니다)

실시

C ++ 프로그램
#include <iostream>
#include <bits/stdc++.h>
using namespace std;

// blueprint of the tree node
class Node
{
    public : 
    int data;
    Node *left, *right, *next;
    
    Node(int key)
    {
        data = key;
        left = right = next = NULL;
    }
};

/* this function performs inorder traversal stores the nodes in various levels */
/* Mapping : int->vector, where int is the level number 
and vector stores all the nodes at a particular 'level'*/
void inorderStore(Node* root,unordered_map<int,vector <int>> &memo,int level)
{
    if(root == NULL)
    return;
    
    inorderStore(root->left,memo,level+1);
    
    /* if a particular level has not been visited so far*/
    if(memo.find(level) == memo.end())
    {
        /* add the level and vector corresponding to it into the map*/
        vector <int> arr = {};
        memo.insert({level,arr});
    }
    /* add nodes into their respective levels*/
    memo[level].push_back(root->data);
    
    inorderStore(root->right,memo,level+1);
    
}

/* function that performs zigzag Traversal
    in similar manner to BFS */
    
void zigzagTraversal(Node *root)
{
    /* create a map */
    unordered_map <int,vector<int> > memo;
    int level = 1;
    
    /* store values into the map(level-wise) using inorder traversal */
    inorderStore(root,memo,level);
    
    /* traverse the map and print nodes by level */
    for(int i=1;i<=memo.size();i++)
    {
        
        if(i%2 == 1)
        {
            for(int j = 0;j<memo[i].size();j++)
            cout<<memo[i][j]<<" ";
        }
        /* alternate levels are to be printed in reverse order to produce zigzag traversal */
        else
        {
            for(int j = memo[i].size()-1;j >= 0;j--)
            cout<<memo[i][j]<<" ";
        }
    }
}

// function to simply perform inorder traversal of the tree
void inorder(Node *root)
{
    if(root == NULL)
    return;
    
    inorder(root->left);
    cout<<root->data<<" ";
    inorder(root->right);
}

int main()
{
    /*create the Binary Tree*/
    Node *root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    root->right->right = new Node(6);
    root->left->left->left = new Node(7);
    root->right->right->right = new Node(8);
    
    zigzagTraversal(root);   
    return 0;
}
1 3 2 4 5 6 8 7
자바 프로그램
import java.util.*;
import java.io.*;

class tutorialCup
{
    // blueprint of the tree node
    static class Node
    {
        int data;
        Node left, right, next;
        
        Node(int key)
        {
            data = key;
            left = right = next = null;
        }
    }

    /* this function performs inorder traversal stores the nodes in various levels */
    /* Mapping : int->vector, where int is the level number 
    and vector stores all the nodes at a particular 'level'*/
    static void inorderStore(Node root,HashMap<Integer,ArrayList<Integer>> memo,int level)
    {
        if(root == null)
        return;
        
        inorderStore(root.left,memo,level+1);
        
        /* if a particular level has not been visited so far*/
        if(!memo.containsKey(level))
        {
            /* add the level and vector corresponding to it into the map*/
            ArrayList <Integer> arr = new ArrayList<>();
            memo.put(level,arr);
        }
        /* add nodes into their respective levels*/
        memo.get(level).add(root.data);
        
        inorderStore(root.right,memo,level+1);
        
    }
    
    /* function that performs zigzag Traversal
        in similar manner to BFS */
    static void zigzagTraversal(Node root)
    {
        /* create a map */
        HashMap <Integer,ArrayList<Integer>> memo = new HashMap<>();
        int level = 1;
        
        /* store values into the map(level-wise) using inorder traversal */
        inorderStore(root,memo,level);
        
        /* traverse the map and print nodes by level */
        for(int i=1;i<=memo.size();i++)
        {
            
            if(i%2 == 1)
            {
                for(int j=0;j<memo.get(i).size();j++)
                System.out.print(memo.get(i).get(j)+" ");
            }
            /* alternate levels are to be printed in reverse order to produce zigzag traversal */
            else
            {
                for(int j=memo.get(i).size()-1;j >= 0;j--)
                System.out.print(memo.get(i).get(j)+" ");
            }
        }
    }

    
    // function to simply perform inorder traversal of the tree
    static void inorder(Node root)
    {
        if(root == null)
        return;
        
        inorder(root.left);
        System.out.print(root.data+" ");
        inorder(root.right);
    }
    
    public static void main (String[] args) 
    {
        /*create the Binary Tree*/
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);
        root.right.right = new Node(6);
        root.left.left.left = new Node(7);
        root.right.right.right = new Node(8);
        
        zigzagTraversal(root);
    }
}
1 3 2 4 5 6 8 7

이진 트리 지그재그 수준 순서 순회에 대한 복잡성 분석

  1. 시간 복잡도 : T (n) = O (nlogn), inorder traversal은 O (n) 시간이 걸립니다. 그러나 각 레벨의 인쇄 노드는 최악의 경우 (전체 바이너리 트리의 경우) O (nlogn)를 사용합니다.
  2. 공간 복잡도 : A (n) = O (n),지도 데이터 구조 사용.

참조