FDU 2021 | 二叉树关键节点的个数

1. 题目描述

给定一颗二叉树，树的每个节点的值为一个正整数。如果从根节点到节点 N 的路径上不存在比节点 N 的值大的节点，那么节点 N 被认为是树上的关键节点。求树上所有的关键节点的个数。请写出程序，并解释解题思路。

输入：3, 1, 4, 3, null, 1, 5
输出：4（图中蓝色节点是关键节点）

2. 我的尝试

这道题麻烦的地方在于输入与建树。由题意可知，输入数据是以完全二叉树形式进行输入的，因此可以考虑直接用数组来存储树，然后再遍历每一个节点并判断其是否为关键节点。

数据的输入是以空格作为分隔符的，因此不适宜直接用 cin进行读入。可以用 getline 函数读入整行，再对读入的字符串遍历进行处理。

#include <bits/stdc++.h>using namespace std;int main() {string str;    // 存储输入的字符串int val = 0;   // 用于计算当前输入节点的值vector<int> tree;int cnt = 0;getline(cin, str);int n = str.size();// 建树for (int i = 0; i < n; i ++) {auto c = str[i];if ('0' <= c && c <= '9') {val = val * 10 + c - '0';} else if (val) {tree.push_back(val);val = 0;} else if (c == 'n') {tree.push_back(-1);}}tree.push_back(val);n = tree.size();// 对除根节点外所有节点遍历，将其与各祖先节点比较，判断是否为关键节点for (int i = 0; i < n && tree[i] != -1; i ++) {int val = tree[i]; bool flag = true;for (int p = (i - 1) / 2; p >= 0; p = (p - 1) / 2) {if (tree[p] > val) flag = false;if (p == 0) break;}if (flag) cnt ++;}// 根节点一定为关键节点，直接加1cnt ++;cout << cnt;
}