[PAT-A] 1155 Heap Paths

Java

import java.io.*;
import java.util.*;

public class Main {
    static int[] tree;
    static int n;
    static List<Integer> path = new ArrayList<>();
    static boolean isGreater = false;
    static boolean isLess = false;

    static void dfs(int u) {
        path.add(tree[u]);

        if (2 * u > n) {
            for (int i = 0; i < path.size(); i++) {
                if (i > 0) System.out.print(" ");
                System.out.print(path.get(i));
            }
            System.out.println();
        }

        if (2 * u + 1 <= n) {
            if (tree[2 * u + 1] < tree[u]) {
                isGreater = true;
            } else {
                isLess = true;
            }
            dfs(2 * u + 1);
        }

        if (2 * u <= n) {
            if (tree[2 * u] < tree[u]) {
                isGreater = true;
            } else {
                isLess = true;
            }
            dfs(2 * u);
        }

        path.remove(path.size() - 1);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(br.readLine());
        tree = new int[n + 1];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) {
            tree[i] = Integer.parseInt(st.nextToken());
        }

        dfs(1);

        if (isGreater && !isLess) {
            System.out.println("Max Heap");
        } else if (!isGreater && isLess) {
            System.out.println("Min Heap");
        } else {
            System.out.println("Not Heap");
        }
    }
}

C++

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

// maxheap: ≤, minheap: ≥

const int N = 1010;

int n;
int tr[N];
vector<int> path;
bool is_greater, is_less;

void dfs(int u) {
    path.push_back(tr[u]);
    if (2 * u > n) {
        for (int i = 0; i < path.size(); ++i) {
            if (i > 0) printf(" ");
            printf("%d", path[i]);
        }
        printf("\n");
    }

    if (2 * u + 1 <= n) {
        if (tr[2 * u + 1] < tr[u]) is_greater = true;
        else is_less = true;
        dfs(2 * u + 1);
    }

    if (2 * u <= n) {
        if (tr[2 * u] < tr[u]) is_greater = true;
        else is_less = true;
        dfs(2 * u);
    }

    path.pop_back();
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d", &tr[i]);

    dfs(1);

    if (is_greater && !is_less) printf("Max Heap\n");
    else if (!is_greater && is_less) printf("Min Heap\n");
    else printf("Not Heap");

    return 0;
}