Traverse Heap PAT Class A 1155 Heap Path

Original title link

In computer science, a heap is a specialized tree-based data structure with heap properties:

If P is the parent node of C, the weight of the P node in the large top heap is greater than or equal to the weight of the C node, and the weight of the P node in the small top heap is less than or equal to the C nodepoint weight.

A common implementation of a heap is a binary heap, which is implemented by a complete binary tree.

To be sure, in a big-top/small-top heap, any path from root to leaf must be in non-increasing/non-decreasing order.

Your task is to check every path in a given complete binary tree to see if it is a heap.

Input format
The first line contains the integer N, which represents the number of nodes in the tree.

The second line contains N distinct integers representing the sequence of level-order traversal of the given complete binary tree.

Output format
For a given tree, first output all paths from root to leaf.

Each path occupies one line, the numbers are separated by spaces, and there must be no extra spaces at the beginning and end of the line.

The paths must be output in the following order: For each node in the tree, the path in its right subtree must be output before the path in its left subtree.

The last line, if it is a large top heap, output Max Heap, if it is a small top heap, output Min Heap, if it is not a heap, output Not Heap.

Data Range
1Input Example 1:
8
98 72 86 60 65 12 23 50
Example output 1:
98 86 23
98 86 12
98 72 65
98 72 60 50
Max Heap
Input Sample 2:
8
8 38 25 58 52 82 70 60
Output Sample 2:
8 25 70
825 82
8 38 52
8 38 58 60
Min Heap
Input Example 3:
8
10 28 15 12 34 9 8 56
Sample output 3:
10 15 8
10 15 9
10 28 34
10 28 12 56
Not Heap

My solution:

#include using namespace std;const int N = 1010;int n;int a[N];bool lt, gt;vector  path;void dfs(int u){path.push_back(a[u]);if(2 * u > n){cout << path[0];for(int i = 1; i < path. size(); i ++ ) {cout << ' ' << path[i];if(path[i] < path[i - 1]) gt = true;else if(path[i] > path[i - 1]) lt = true;}cout << endl;}if(2 * u + 1 <= n) dfs(2 * u + 1);if(2 * u <= n) dfs(2 * u);path.pop_back();}int main(){cin >> n;for(int i = 1; i <= n; i ++ ){cin >> a[i];}dfs(1);if(lt && gt) puts("Not Heap");else if(lt) puts("Min Heap");else puts("Max Heap");return 0;}