简答题 偏难
#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] &amp;= chk[l[u]] &amp; 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:左子树叶子最小深度 &gt;= 右子树叶子最大深度     chk[u] &amp;= mn[l[u]] &gt;= mx[r[u]]     # 条件3:整棵子树叶子最小深度 &gt;= 最大深度 - 1     chk[u] &amp;= mn[u] &gt;= mx[u] - 1     # 如果u是完全二叉树,答案+1     ans += chk[u] dfs(1) print(ans)</pre>
这道题暂未补解析。