用Python计算树的深度

Question

定义一个函数sum_to_deepest(root)，该函数返回从根到最深的叶的键的和，在根为根的树中。如果有两片最深的叶子，则返回较大的和；如果根没有，则返回0。

在这个问题中，您会发现定义一个helper函数有助于同时返回最深叶的深度和该叶路径上的总和。

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

从一开始

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)