网站开发公司规章制度,58同城盐城网站建设,成都十大互联网公司,dw网站站点正确建设方式文章目录 1. 题目描述2. 我的尝试 1. 题目描述
给定一颗二叉树#xff0c;树的每个节点的值为一个正整数。如果从根节点到节点 N 的路径上不存在比节点 N 的值大的节点#xff0c;那么节点 N 被认为是树上的关键节点。求树上所有的关键节点的个数。请写出程序#xff0c;并… 文章目录 1. 题目描述2. 我的尝试 1. 题目描述
给定一颗二叉树树的每个节点的值为一个正整数。如果从根节点到节点 N 的路径上不存在比节点 N 的值大的节点那么节点 N 被认为是树上的关键节点。求树上所有的关键节点的个数。请写出程序并解释解题思路。 输入3, 1, 4, 3, null, 1, 5 输出4图中蓝色节点是关键节点 2. 我的尝试
这道题麻烦的地方在于输入与建树。由题意可知输入数据是以完全二叉树形式进行输入的因此可以考虑直接用数组来存储树然后再遍历每一个节点并判断其是否为关键节点。
数据的输入是以空格作为分隔符的因此不适宜直接用 cin进行读入。可以用 getline 函数读入整行再对读入的字符串遍历进行处理。
#include bits/stdc.husing namespace std;int main() {string str; // 存储输入的字符串int val 0; // 用于计算当前输入节点的值vectorint 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;
}
