自下而上，从右至左的层序遍历

ゝ一世哀愁。 2023-08-17 16:55 92阅读 0赞

普通的层序遍历是自下而上，从左至右； 这里刚好相反， 对于这样的问题，一般采用栈，栈能够实现序列的逆序。      因此，普通的层序遍历+栈，就能够解决这个问题。

1 #include<bits\stdc++.h>
     2 using namespace std;
     3 
     4 struct node {
     5     int data;
     6     node* left = nullptr, * right = nullptr;
     7 };
     8 
     9 typedef struct node Node;
    10 
    11 Node* CreateTree() {
    12     Node* root = new Node;
    13     root->data = 1;
    14     root->left = new Node;
    15     root->left->data = 2;
    16     root->right = new Node;
    17     root->right->data = 3;
    18     root->left->left = new Node;
    19     root->left->left->data = 4;
    20     root->left->right = new Node;
    21     root->left->right->data = 5;
    22     root->right->left = new Node;
    23     root->right->left->data = 6;
    24     root->right->right = new Node;
    25     root->right->right->data = 7;
    26     return root;
    27 }
    28 
    29 // 
    30 void ReverseLevelTravel(Node* root) {
    31     if (root != nullptr) {
    32         queue<Node*> q;
    33         stack<Node*> s;
    34         q.push(root);
    35 
    36         while (!q.empty()) {
    37             root = q.front();
    38             s.push(root);   // 将出队的元素放入栈中
    39             q.pop();
    40             if (root->left != nullptr) {
    41                 q.push(root->left);
    42             }
    43             if (root->right != nullptr) {
    44                 q.push(root->right);
    45             }
    46         }
    47 
    48         while (!s.empty()) {
    49             root = s.top();
    50             s.pop();
    51             cout << root->data << " ";
    52         }
    53     }
    54 }
    55 
    56 int main() {
    57     Node* root = CreateTree();
    58     ReverseLevelTravel(root);
    59     return 0;
    60 }

转载于:https://www.cnblogs.com/yy-1046741080/p/11539722.html