简答题
偏难
#16723
完全二叉树
完全二叉树
答案与解析
正确答案:<pre class="brush:python;toolbar:false;">n = int(input())
# l[i]:i的左孩子;r[i]:i的右孩子,0为空
l = [0] * (n + 1)
r = [0] * (n + 1)
# mn[u]:u子树中,叶子节点的最小深度
mn = [0] * (n + 1)
# mx[u]:u子树中,叶子节点的最大深度
mx = [0] * (n + 1)
# chk[u]:布尔标记,1代表以u为根的子树是完全二叉树,0不是
chk = [0] * (n + 1)
ans = 0
for i in range(1, n + 1):
li, ri = map(int, input().split())
l[i] = li
r[i] = ri
def dfs(u):
global ans
chk[u] = 1
if u == 0:
return
# 后序:先递归左右子树
dfs(l[u])
dfs(r[u])
# 条件1:左右子树本身都必须是完全二叉树
chk[u] &= chk[l[u]] & chk[r[u]]
# mn[u]:当前子树叶子最小深度
mn[u] = 1 + min(mn[l[u]], mn[r[u]])
# mx[u]:当前子树叶子最大深度
mx[u] = 1 + max(mx[l[u]], mx[r[u]])
# 条件2:左子树叶子最小深度 >= 右子树叶子最大深度
chk[u] &= mn[l[u]] >= mx[r[u]]
# 条件3:整棵子树叶子最小深度 >= 最大深度 - 1
chk[u] &= mn[u] >= mx[u] - 1
# 如果u是完全二叉树,答案+1
ans += chk[u]
dfs(1)
print(ans)</pre>
这道题暂未补解析。