树上摘樱桃

[编程题]树上摘樱桃

热度指数：1709 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

有一棵二叉树，树上的叶子节点定义为“樱桃”。现在需要找出树上有多少个满足如下子结构的“樱桃”串，即一串上刚好有两颗“樱桃”。

比如如下的一棵树，红框标示的有两个符合要求的结构，答案就是2

又比如下面的这颗树，没有任何符合要求的子结构，则答案是0

输入描述:

第一行两个正整数m, n，空格分开，分别代表总共有树上有多少个节点，和树上有多少条边，2<=m<=100,  1<=n<=100
下面有n行，每行为3个部分，用空格分割，第一个数字为某非叶子节点的id, 第二个为该边为left还是right，第三个为子节点的id
注意：节点id彼此不会重复，id 1为根节点

输出描述:

一个整数，标示符合要求的子结构的数量

示例1

输入

10 9
1 left 2
1 right 3
2 left 4
2 right 5
3 right 6
6 left 7
6 right 8
8 left 9
8 right 10

输出

说明

如题目说明的第一个样例图，可以看到，2-4-5子串，8-9-10子串，两个子串符合条件，所以答案为2

算法知识视频讲解

Python

榖錬

line = input().split()
node_num = int(line[0])
bian_num = int(line[1])
class TreeNode:
def __init__(self,val):
self.left = None
self.right = None
self.val = val

def postorder(node):
if not node:
return 0
if not node.left and not node.right:
return 1
l = postorder(node.left)
r = postorder(node.right)
if l == 1 and r == 1:
return 2
l = 0 if l < 2 else l
r = 0 if r < 2 else r
return l + r

dic = dict()
for num in range(1,node_num+1):
dic[num] = TreeNode(num)
for i in range(bian_num):
line = input().split()
a = int(line[0])
op = line[1]
b = int(line[2])
node_a = dic[a]
node_b = dic[b]
if op == "left":
node_a.left = node_b
else:
node_a.right = node_b
root = dic[1]
print(postorder(root)//2)

发表于 2021-08-21 10:02:33 回复(0)