网易笔试

#include<vector>
#include<queue>
#include<algorithm>
using namespace std;

//dfs求每个节点的高度，k为所求节点
void getDepth(const vector<vector<int> >&tree, vector<int>&depth, int k)
{
if (tree[k][1] == -1 && tree[k][2] == -1)
{
depth[k] = 1;
return;
}
else if (tree[k][1] != -1)
{
if (depth[tree[k][1]] == 0)
getDepth(tree, depth, tree[k][1]);
depth[k] = depth[tree[k][1]] + 1;
}
else if (tree[k][2] != -1)
{
if (depth[tree[k][2]] == 0)
getDepth(tree, depth, tree[k][2]);
depth[k] = depth[tree[k][2]] + 1;
}
else
{
if (depth[tree[k][1]] == 0)
getDepth(tree, depth, tree[k][1]);
if (depth[tree[k][2]] == 0)
getDepth(tree, depth, tree[k][2]);
depth[k] = max(depth[tree[k][1]], depth[tree[k][2]]) + 1;
}
}

int main()
{
int T = 0;
cin >> T;

vector<bool>res(T, false);
for (int i = 0; i<T; ++i)
{
int N = 0;
cin >> N;
if (N <= 0)
continue;

//用二维数组存树结构,二维数组行数代表节点号,每行三列分别代表val,leftChild,rightChild
vector<vector<int> >tree(N, vector<int>(3, -1));
for (int i = 0; i<N; ++i)
{
int value, left, right;
cin >> value >> left >> right;
tree[i][0] = value;
tree[i][1] = left;
tree[i][2] = right;
}

//找根节点,高度最高的为根节点
vector<int>depth(N, 0);
for (int i = 0; i<N; ++i)
{
getDepth(tree, depth, i);
}
auto it = max_element(depth.begin(), depth.end());
int root = it - depth.begin();

//bfs层序遍历,用了两个队列,一个队列保存这列节点，一个保存下列节点(用一个队列也可以）
queue<int>q[2];
int index = 0;
int cur = tree[root][0];
bool isIncr = true;
q[index].push(root);
while (!q[0].empty() || !q[1].empty())
{
int next = 0;
while (!q[index % 2].empty())
{
int now = q[index % 2].front();
q[index % 2].pop();
if (tree[now][1] != -1)
{
q[(index + 1) % 2].push(tree[now][1]);
next += tree[tree[now][1]][0];
}
if (tree[now][2] != -1)
{
q[(index + 1) % 2].push(tree[now][2]);
next += tree[tree[now][2]][0];
}
}
if (next != 0 && cur >= next)
{
isIncr = false;
break;
}

index++;
cur = next;
res[i] = isIncr;
}

for (auto r : res)
{
if (r)
cout << "YES" << endl;
else
cout << "NO" << endl;
}

system("pause");
return 0;
}
#笔试题目##网易#