python-左孩子右兄弟

解题思路:

参考博客:https://blog.csdn.net/qq_52652816/article/details/122333311

具体思路可以参考上面连接。

我用python分别写了递归的解法和动态数组的解法，但都超时了，73分。

思路是一样的，其实时间复杂度两种方法也差不多。

注意事项:

参考代码:

递归：

def dfs(node):  
    global Tree  
      
    m = 0  
    for i in range(len(Tree[node])):  
        m = max(m,dfs(Tree[node][i]))  
  
    return m + len(Tree[node])  
  
  
if __name__ == '__main__':  
    n = int(input())  
    Tree = [[] for i in range(n+1)]  
    for i in range(2,n+1):  
        f = int(input())  
        Tree[f].append(i)  
  
    maxheight = dfs(1)  
    print(maxheight)

动态数组：

def f(n):  
    Tree = [[] for i in range(n+1)]  
    for i in range(2,n+1):  
        f = int(input())  
        Tree[f].append(i)  
  
    dp = [0 for i in range(n+1)]  
    for i in range(n,0,-1):  
        for j in range(len(Tree[i])):  
            dp[i] = max(dp[i],len(Tree[i]) + dp[Tree[i][j]])  
  
    print(dp[1])  
  
  
if __name__ == '__main__':  
    n = int(input())  
    f(n)