笔试时间：2023年3月15日 春招实习

第一题

题目：满子二叉树

给定一棵二又树，试求这棵二叉树有多少个节点满足以该节点为根的子树是满二叉树？我们定义一棵树是满二叉树，当且仅当每一层的节点数量都达到了最大值(即无法在这一层添加新节点)。

输入描述

第一行输入一个正整数n，代表节点的数量。接下来的n行，第i行输入两个整数li和ri，代表i号节点的左儿子和右儿子。请注意，如果一个节点没有左儿子/右儿子，则对应的li和ri为-1。

输出描述

子树为满二又树的节点数量。

示例输入

5

2 3

4 5

-1 -1

-1 -1

-1 -1

示例输出

4

说明

2、3、4、5号节点的子树都是满二叉树。

参考题解

Python：[此代码未进行大量数据的测试，仅供参考]

n = int(input())
class TreeNode:
    def __init__(self, val, left, right):
        self.val = val
        self.left = left
        self.right = right

trees = [TreeNode(i,None, None) for i in range(n + 1)]

for i in range(1, n + 1):
    l, r = map(int, input().split(" "))
    trees[i].left = trees[l] if l != -1 else None
    trees[i].right = trees[r] if r != -1 else None

heights = [0 for _ in range(n + 1)]

def getheights(node):
    if not node: return 0
    heights[node.val] = max(getheights(node.left), getheights(node.right)) + 1
    return heights[node.val]

getheights(trees[1])

res = 0

def dfs(node):
    if not node: return 0
    cur = 1 + dfs(node.left) + dfs(node.right)
    global res
    if cur == 2**(heights[node.val]) - 1:
        res += 1
    return cur

dfs(trees[1])
print(res)

第二题

题目：合法的三元组

给定一个数组，请你计算有多少个三元组< i,j,k >满足0≤i<j<k<n且max(ai,aj,ak)−min(ai,aj,ak)=1。

输入描述

第一行输入一个正整数n。第二行输入n个正整数ai  3≤n≤200000

1≤a≤10^9

输出描述

一个整数，代表合法的三元组数量。

示例输入

4

2 2 3 1

示例输出

2

参考题解

C++：[此代码未进行大量数据的测试，仅供参考]

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n);

    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    unordered_map<int, int> dict;