跳转至

相同值的子树个数

1、题目描述

子树: T的子树

树的高度:

从根节点开始,最长的边的长度

注意:

  • 如果是是空的,返回-1
  • 如果子树所有的值都是相同的,数量加一
  • 叶子节点是一棵满足条件的子树
  • 如果只有一个节点,返回1

输入格式:

  • 第一行数字n,表示数的高度,也就是最长边的数量
  • 接下来有n+1行,从根节点开始的层次遍历

限制:

  • -1 <= height <= 20
  • 0<= node <= 500

实例1:

输入:

3
6
4 3
4 4 5 5
4 4 4 4 5 5 5 5

image-20191124193036306

输出:

13

值全部为4的子树有7棵,为5的有6棵,一共13

实例2:

输入:

2
3
3 15
-1 -1 15 15

输出:

4

值为3的子树有1棵,-1代表节点为Null,值为15的子树有3棵,一共为4

2、解题思路

一棵树,如果所有的值都是相等的,例如一共三个节点,那么满足条件的子树就为3,也就是节点的数量

如果一个节点的值与父节点不同,那么我们认为父节点所对应的就是不满足条件的

因此,根据这个思路,假设有15个节点,首先设置一个长度是15的数组,初始值都为1

从根节点开始判断,一旦遇到子节点和父节点的值不相同的时候,就将父节点以及父节点到根节点路径上的带你都置为0,这样最终留下的节点就是满足条件的,直接加和返回即可

实际判断的时候,只需要判断到父节点为0即可返回,不需重复清零

def clean_parent(cur_node):
    parent = 0 if cur_node == 0 else (cur_node - 1) // 2
    while mark[parent]:
        mark[parent] = 0
        parent = 0 if parent == 0 else (parent - 1) // 2


n = int(input().strip())
if n == -1:
    print("-1")

index = 0
mark = [1] * (2 ** (n + 1) - 1)
mapping = {}

for _ in range(n + 1):
    for num in map(int, input().strip().split()):
        mapping[index] = num
        if num == -1:
            mark[index] = 0
        else:
            parent = 0 if index == 0 else (index - 1) // 2
            if num != mapping[parent]:
                clean_parent(index)
        index += 1

print(sum(mark))