题目分析

遇到树形的问题，肯定要想到深搜和广搜，但是这个题目并不是一个树，只是一些邻接关系，没有left和right节点。如何转换到树的思想？当然可以创建树，但是还需要写递归创建树结构，思路不是非常好，小伙伴们能否使用数组容器实现呢？

DFS

我们可以使用二维数组保存，第一个维度大小是101，代表最多101个结点，第二个维度大小是2，分别代表左孩子和右孩子。因为节点从1开始，因此我们初始值设为0，进行DFS，当某个节点的两个孩子都不为0，并且每个孩子的两个孩子都为0，则计数器+1。算法的**时间复杂度为$O(n)$，空间复杂度为$O(n)$**。

import sys


def dfs(current):
    global res
    if dic[current][0] and dic[dic[current][0]] == leaf and dic[current][1] and dic[dic[current][1]] == leaf:
        res += 1
        return
    for child in dic[current]:
        if child:
            dfs(child)


for line in sys.stdin:
    m, n = [int(x) for x in line.strip().split()]
    leaf = [0, 0]
    dic = [[0, 0] for _ in range(101)]
    for _ in range(n):
        p, relation, c = sys.stdin.readline().strip().split()
        p, c = int(p), int(c)
        if relation == 'left':
            dic[p][0] = c
        else:
            dic[p][1] = c
    res = 0
    dfs(1)
    print(res)

BFS

思路和DFS相同，只是搜索方式是按层搜索，直接看代码即可。算法的**时间复杂度为$O(n)$，空间复杂度为$O(n)$**。

import sys
from collections import deque


for line in sys.stdin:
    m, n = [int(x) for x in line.strip().split()]
    leaf = [0, 0]
    dic = [[0, 0] for _ in range(101)]
    for _ in range(n):
        p, relation, c = sys.stdin.readline().strip().split()
        p, c = int(p), int(c)
        if relation == 'left':
            dic[p][0] = c
        else:
            dic[p][1] = c
    res = 0

    queue = deque([1])
    while queue:
        current = queue.popleft()
        if dic[current][0] and dic[dic[current][0]] == leaf and dic[current][1] and dic[dic[current][1]] == leaf:
            res += 1
            continue
        for child in dic[current]:
            if child:
                queue.append(child)
    print(res)

数学

严格意义来说不是一种数学推导，但是又具有数学的逆向思维思路，勉强归为数学部分吧。
我们将每一个关系读入，将父节点保存在父节点哈希表中，将子节点加入到子节点哈希表中，让子节点哈希表减父节点哈希表，则可以得到叶子节点的哈希表。并且在读入时维护一个从子节点指向父节点的字典。我们对每个叶子节点寻找其父节点，如果某个父节点出现两次，说明该父节点有两个叶子节点，给计数器+1即可。在Python中可以from collections import Counter，这时一个计数器，当某个父节点的计数器值为2时，说明该父节点是满足条件的。算法的**时间复杂度为$O(n)$，空间复杂度为$O(n)$**。

import sys
from collections import Counter

for line in sys.stdin:
    m, n = [int(x) for x in line.strip().split()]
    dic = dict()
    node = set()
    not_leaf = set()
    for _ in range(n):
        p, relation, c = sys.stdin.readline().strip().split()
        p, c = int(p), int(c)
        node.add(c)
        not_leaf.add(p)
        dic[c] = p
    leaf = node - not_leaf
    res = len(list(filter(lambda x: x == 2, Counter([dic[leaf_node] for leaf_node in leaf]).values())))
    print(res)

刷题总结

这时一种BFS和DFS的变形题目，通过数组记录父子关系，这种题和leetcode的题型不同，因为leetcode是只需要写函数实现，因此输入输出已经定义好了树形结构，直接搜索即可。而牛客网的题型需要自己读入数据，如果需要创建树结构，则需要自己定义构造函数，所以并不是很方便，这时候通过其他方式保存树结构就非常重要。