Рубрики

Проверьте, приводит ли обратный порядок уровней двоичного дерева к палиндрому

Деревья, Структуры данных

Дано бинарное дерево и задание, если проверить, приводит ли его обход уровня порядка к палиндрому или нет.

Примеры:

Input:

Output: Yes
RADAR is the level order traversal of the
given tree which is a palindrome.

Input:

Output: No

Подходить:

  • Пройдите двоичное дерево в порядке уровней и сохраните узлы в стеке.
  • Обходите двоичное дерево в порядке уровней еще раз и сравните данные в узле с данными в верхней части стека.
  • В случае совпадения перейдите к следующему узлу.
  • В случае несоответствия остановите и напечатайте №

Ниже приведена реализация вышеуказанного подхода:

C ++

// C ++ реализация подхода
#include <bits/stdc++.h>

using namespace std;

  
// Структура для узла дерева

struct node {

    char data;

    node *left, *right;

};

  
// Функция для добавления узла
// к бинарному дереву

node* add(char data)

{

    node* newnode = new node;

    newnode->data = data;

    newnode->left = newnode->right = NULL;

    return newnode;

}

  
// Функция для выполнения обхода уровня
// двоичного дерева и добавляем узлы в
// стек

void findInv(node* root, stack<node*>& S)

{

    if (root == NULL)

        return;

  

    // Очередь содержит узлы, которые находятся

    // обрабатывается начиная с корня

    queue<node*> Q;

    Q.push(root);

    while (Q.size()) {

        node* temp = Q.front();

        Q.pop();

  

        // Вынимаем узел из очереди

        // и помещаем его в стек

        S.push(temp);

  

        // Если есть левый ребенок

        // затем помещаем его в очередь

        if (temp->left != NULL)

            Q.push(temp->left);

  

        // Если есть правильный ребенок

        // затем помещаем его в очередь

        if (temp->right != NULL)

            Q.push(temp->right);

    }

}

  
// Функция, которая возвращает true, если
// уровень порядка обхода
// дерево приводит к палиндрому

bool isPalindrome(stack<node*> S, node* root)

{

    queue<node*> Q;

    Q.push(root);

    while (Q.size()) {

  

        // Для сохранения элемента в

        // фронт очереди

        node* temp = Q.front();

  

        // Для сохранения элемента в

        // вершина стека

        node* temp1 = S.top();

        S.pop();

        Q.pop();

  

        // Если данные в узле сверху

        // стека не соответствует данным

        // в узле в начале очереди

        if (temp->data != temp1->data)

            return false;

        if (temp->left != NULL)

            Q.push(temp->left);

        if (temp->right != NULL)

            Q.push(temp->right);

    }

  

    // Если нет несоответствия

    return true;

}

  
// Код драйвера

int main()

{

  

    // Создание бинарного дерева

    node* root = add('R');

    root->left = add('A');

    root->right = add('D');

    root->left->left = add('A');

    root->left->right = add('R');

  

    // Стек для хранения узлов

    // дерево в порядке обхода уровня

    stack<node*> S;

    findInv(root, S);

  

    // Если прохождение порядка уровня

    // приводит к палиндрому

    if (isPalindrome(S, root))

        cout << "Yes";

    else

        cout << "NO";

  

    return 0;

}

Джава

// Java реализация подхода

import java.util.*;

  

class GFG

{

  
// Структура для узла дерева

static class node

{

    char data;

    node left, right;

};

  
// Функция для добавления узла
// к бинарному дереву

static node add(char data)

{

    node newnode = new node();

    newnode.data = data;

    newnode.left = newnode.right = null;

    return newnode;

}

  
// Функция для выполнения обхода уровня
// двоичного дерева и добавляем узлы в
// стек

static void findInv(node root, Stack<node> S)

{

    if (root == null)

        return;

  

    // Очередь содержит узлы, которые находятся

    // обрабатывается начиная с корня

    Queue<node> Q = new LinkedList<>();

    Q.add(root);

    while (Q.size() > 0) 

    {

        node temp = Q.peek();

        Q.remove();

  

        // Вынимаем узел из очереди

        // и помещаем его в стек

        S.add(temp);

  

        // Если есть левый ребенок

        // затем помещаем его в очередь

        if (temp.left != null)

            Q.add(temp.left);

  

        // Если есть правильный ребенок

        // затем помещаем его в очередь

        if (temp.right != null)

            Q.add(temp.right);

    }

}

  
// Функция, которая возвращает true, если
// уровень порядка обхода
// дерево приводит к палиндрому

static boolean isPalindrome(Stack<node> S, node root)

{

    Queue<node> Q = new LinkedList<>();

    Q.add(root);

    while (Q.size() > 0) 

    {

  

        // Для сохранения элемента в

        // фронт очереди

        node temp = Q.peek();

  

        // Для сохранения элемента в

        // вершина стека

        node temp1 = S.peek();

        S.pop();

        Q.remove();

  

        // Если данные в узле сверху

        // стека не соответствует данным

        // в узле в начале очереди

        if (temp.data != temp1.data)

            return false;

        if (temp.left != null)

            Q.add(temp.left);

        if (temp.right != null)

            Q.add(temp.right);

    }

  

    // Если нет несоответствия

    return true;

}

  
// Код драйвера

public static void main(String[] args)

{

  

    // Создание бинарного дерева

    node root = add('R');

    root.left = add('A');

    root.right = add('D');

    root.left.left = add('A');

    root.left.right = add('R');

  

    // Стек для хранения узлов

    // дерево в порядке обхода уровня

    Stack<node> S = new Stack<node>();

    findInv(root, S);

  

    // Если прохождение порядка уровня

    // приводит к палиндрому

    if (isPalindrome(S, root))

        System.out.print("Yes");

    else

        System.out.print("NO");

}
}

  
// Этот код предоставлен 29AjayKumar

C #

// C # реализация подхода

using System;

using System.Collections.Generic;

  

class GFG

{

  
// Структура для узла дерева

class node

{

    public char data;

    public node left, right;

};

  
// Функция to.Добавить узел
// к бинарному дереву

static node add(char data)

{

    node newnode = new node();

    newnode.data = data;

    newnode.left = newnode.right = null;

    return newnode;

}

  
// Функция для выполнения обхода уровня
// Двоичного дерева и. Добавляем узлы в
// стек

static void findInv(node root, Stack<node> S)

{

    if (root == null)

        return;

  

    // Очередь содержит узлы, которые находятся

    // обрабатывается начиная с корня

    Queue<node> Q = new Queue<node>();

    Q.Enqueue(root);

    while (Q.Count > 0) 

    {

        node temp = Q.Peek();

        Q.Dequeue();

  

        // Вынимаем узел из очереди

        // и помещаем его в стек

        S.Push(temp);

  

        // Если есть левый ребенок

        // затем помещаем его в очередь

        if (temp.left != null)

            Q.Enqueue(temp.left);

  

        // Если есть правильный ребенок

        // затем помещаем его в очередь

        if (temp.right != null)

            Q.Enqueue(temp.right);

    }

}

  
// Функция, которая возвращает true, если
// уровень порядка обхода
// дерево приводит к палиндрому

static bool isPalindrome(Stack<node> S, 

                               node root)

{

    Queue<node> Q = new Queue<node>();

    Q.Enqueue(root);

    while (Q.Count > 0) 

    {

  

        // Для сохранения элемента в

        // фронт очереди

        node temp = Q.Peek();

  

        // Для сохранения элемента в

        // вершина стека

        node temp1 = S.Peek();

        S.Pop();

        Q.Dequeue();

  

        // Если данные в узле сверху

        // стека не соответствует данным

        // в узле в начале очереди

        if (temp.data != temp1.data)

            return false;

        if (temp.left != null)

            Q.Enqueue(temp.left);

        if (temp.right != null)

            Q.Enqueue(temp.right);

    }

  

    // Если нет несоответствия

    return true;

}

  
// Код драйвера

public static void Main(String[] args)

{

  

    // Создание бинарного дерева

    node root = add('R');

    root.left = add('A');

    root.right = add('D');

    root.left.left = add('A');

    root.left.right = add('R');

  

    // Стек для хранения узлов

    // дерево в порядке обхода уровня

    Stack<node> S = new Stack<node>();

    findInv(root, S);

  

    // Если прохождение порядка уровня

    // приводит к палиндрому

    if (isPalindrome(S, root))

        Console.Write("Yes");

    else

        Console.Write("NO");

}
}

  
// Этот код предоставлен Rajput-Ji

Выход:

Yes

Рекомендуемые посты:

Проверьте, приводит ли обратный порядок уровней двоичного дерева к палиндрому

0.00 (0%) 0 votes