个人练习-PAT甲级-1110 Complete Binary Tree

题目链接https://pintia.cn/problem-sets/994805342720868352/problems/994805359372255232

题目大意：给出一棵树的结构，判断是否为完全二叉树。如果是，输出YES和最后一个节点的index；否则输出NO和根节点index

思路：建树，找到根节点。然后遍历树，给每个节点赋值一个val，从1开始，那么二叉树，左儿子val = val*2，右儿子val = val*2 + 1。因为节点数N已知，所以合法（是完全二叉树）时这个val <= N，在val == N的时候得到最后一个节点；否则不是完全二叉树，直接return停止遍历，出来输出结果就行。

void inOrder(int idx, int val) {
    if (ret == true) {
        if (tree[idx].left != -1)
            inOrder(tree[idx].left, val * 2);

        tree[idx].val = val;
        if (val > N){
            ret = false;
            return;
        }
        else if (val == N)
            last_idx = idx;

        if (tree[idx].right != -1)
            inOrder(tree[idx].right, val * 2 + 1);
    }
}

完整代码

#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>
#include <set>

using namespace std;


class Node{
public:
    int val;
    int left, right;
};

int N, last_idx;
vector<Node> tree;
vector<bool> isRoot;
bool ret;


void inOrder(int idx, int val) {
    if (ret == true) {
        if (tree[idx].left != -1)
            inOrder(tree[idx].left, val * 2);

        tree[idx].val = val;
        if (val > N){
            ret = false;
            return;
        }
        else if (val == N)
            last_idx = idx;

        if (tree[idx].right != -1)
            inOrder(tree[idx].right, val * 2 + 1);
    }
}


int main() {
    scanf("%d\n", &N);
    tree.resize(N);
    isRoot.resize(N, true);
    ret = true;

    for (int i = 0; i < N; i++) {
        string str1, str2;
        cin >> str1 >> str2;
        if (str1[0] != '-') {
            tree[i].left = stoi(str1);
            isRoot[stoi(str1)] = false;
        }
        else
            tree[i].left = -1;

        if (str2[0] != '-') {
            tree[i].right = stoi(str2);
            isRoot[stoi(str2)] = false;
        }
        else
            tree[i].right = -1;
    }

    int root = -1;
    for (int i = 0; i < N; i++) {
        if (isRoot[i] == true) {
            root = i;
            break;
        }
    }

    inOrder(root, 1);

    if (ret == true)
        printf("YES %d", last_idx);
    else
        printf("NO %d", root);


    return 0;
}