通过使用队列显示反向级别订单遍历

题：

给定一个二叉树根节点，以反向级别遍历显示所有节点。

例：

考虑下面给出的图像：

如上图所示，反向级别遍历为：7，15，18，30，10，25，16

解：

解决方案类似于级别顺序遍历，但有一个区别。

在这里，我们应该使用堆栈和队列。

这里的想法是进行级别顺序遍历，同时使元素出队，将这些元素推入堆栈。

将元素推入堆栈时，先推右孩子，然后推左孩子。

例：

1.如果我们只有一个节点，如下所示：

根节点不’t具有左或右节点。因此，从队列中删除并放入堆栈。由于树为空，因此从堆栈中删除并显示。

2.如果我们有2个节点，如下所示：

首先将根节点插入队列。
从队列中弹出并插入堆栈。

队列：空
堆叠：16

接下来转到合适的孩子，并插入队列

队：25
堆叠：16

接下来转到左孩子，并插入队列

队列：25，10
堆叠：16

现在，弹出两个元素并插入堆栈

列：NULL
堆叠：16，10，25

由于树为NULL，因此显示堆栈内容。

C ++解决方案

#include <iostream>
#include <queue>
#include <stack>
using namespace std;

// structure to hold binary tree node
struct Node
{
    int data;
    Node *left, *right;

    Node(int data)
    {
        this->data = data;
        this->left = this->right = nullptr;
    }
};


void display_reverse_level_order(Node *root) 
{ 
    stack <Node *> my_stack; 
    queue <Node *> my_queue; 
    my_queue.push(root); 
  

    while (my_queue.empty() == false) 
    { 
        // Dequeue node and make it root
        root = my_queue.front(); 
        my_queue.pop(); 
        my_stack.push(root); 
  
        // Enqueue right child 
        if (root->right) 
            my_queue.push(root->right);
  
        // Enqueue left child 
        if (root->left) 
            my_queue.push(root->left); 
    } 
  
    // display all the elements in stack 
    while (my_stack.empty() == false) 
    { 
        root = my_stack.top(); 
        cout << root->data << " "; 
        my_stack.pop(); 
    } 
} 

int main()  
{  
    Node* root = nullptr;
    /* Binary tree:
              16
            /   \
           /     \
          10      25
         /  \    /  \
        /    \  /    \
       7    15 18     30

    */

    root = new Node(16);
    root->left = new Node(10);
    root->right = new Node(25);
    root->left->left = new Node(7);
    root->left->right = new Node(15);
    root->right->left = new Node(18);
    root->right->right = new Node(30);

    int level = 2;

    cout<<"Solution = " <<endl;
    display_reverse_level_order(root); 

    return 0;  
}

输出：

Solution =
7 15 18 30 10 25 16