在Python中计算树的深度

Question

定义一个函数sum_to_deepest(root),该函数返回以root为根的树中从根到最深叶的键的总和.如果有两个最深的叶子,则返回较大的总和; 如果根是None,则返回0.

在这个问题中,您会发现帮助定义一个辅助函数,它返回最深叶子的深度和沿叶子路径的总和.

Answer 1

你真的不应该在这里问它的答案.先尝试一下.我只会给你提示和伪代码.

节点具有属性left, right, key.

要计算高度,可以递归地进行.您需要使用左右子树的较大高度并添加1.

想像

    A
   / \
  B   C 
 /
D

伪代码:

height(node)-> 
    if(node is a leaf) return 0
    return maximum(height(left subtree), height(right subtree)) + 1

从A开始,

height(A) -> maximum(height(B), height(C) + 1
height(B) -> maximum(height(D), null) + 1
height(D) -> 0
height(B) -> 1
height(C) -> 0
height(A) -> maximum(1, 0) + 1 = 2

为了获得总和,您需要确定树下面的哪条路径将带您到最深的叶子.最深的叶子的高度将沿着具有更高高度的子树的路径,所以像这样(伪代码):

sum_to_deepest(node) -> 
    if(node is null) return 0
    leftheight = height(left subtree)
    rightheight = height(right subtree)
    if(leftheight > rightheight) then
        return (current key) + sum_to_deepest(left subtree)
    return (current key) + sum_to_deepest(right subtree)