python - 查找二叉搜索树的最深和的函数

Question

我正在尝试在 python 中创建一个函数，但我根本不想更改 BST 类来执行此操作。函数是求根到深度最大的节点的路径之和。如果有多个节点具有相同的深度，我正在寻找它的最大总和并返回它。

到目前为止我得到了什么(使用基本的 BST 类)

类 BTNode(对象):

    def __init__(self, data, left=None, right=None):

        self.data = data
        self.left = left
        self.right = right

在尝试制作一个算法来解决这个问题一段时间后，我想出了上面的几个，但它们都失败了，我不知道如何编码。

算法:

我认为这可行:

我们从根开始。 (我认为基本情况应该是每当我们击中叶子时，当节点中没有 child 时，所以没有左 child 或右 child ，以及当有左没有右，或者有右没有左时)

我首先检查左子树并获取它的深度，我们将其与总和一起称为 depth_L。然后我检查右子树，我们将其称为 depth_R，然后获取它的深度及其总和。

第二个条件是检查它们是否相等，如果它们相等则很容易，我们只需取两个深度的最大总和。否则我们会看看谁拥有最高的深度并尝试获得它的总和。

现在有几件事我不知道该怎么做。

1:我从来没有学过可选参数，所以我在尝试这个练习时试图避免这种情况，但我认为我做不到，我真的很感激有人可以向我展示一些很酷的辅助函数。

2:不是右边的总和，也不是左边的总和，是我需要的路径。想办法得到刚好路径有点迷惑

(这是我使用上述算法的新尝试):

    def deepest_sum(self, bsum = 0, depth = 0):

        # The root is in every path so
        bsum = bsum + self.data
        depth = depth + 1
        # Base case whenever we find a leaf
        if self.left == None and self.right == None:
            result = bsum,depth

        elif self.left is not None and self.right is None:
            pass

        elif self.left is None and self.right is not None:
            pass

        else:

            # Getting the left and right subtree's depth as well as their
            # sums, but once we hit a leaf it will stop 
            # These optional parameters is messing me up
            if self.left:
                (sums1, depth_L) = self.left.deepest_sum(bsum,depth)
            if self.right:
                (sums2, depth_R) = self.right.deepest_sum(bsum,depth)

            # The parameter to check if they are equal, the highest goes through
            if depth_L == depth_R:
                result = max(sums1, sums2), depth_R
            else:
                if depth_L > depth_R:
                    result = sums1, depth_L
                else:
                    result = sums2, depth_R

        return result

坚持我提到的部分。这是一个例子:

>>> BST(8, BST(7, BST(10), BST(11)), BST(6, BST(11), BST(9, None, BST(14)))

37  (depth 3 is the highest so 8 + 6 + 9 + 14 is the path) 

对不起，我把 BST 忘了，它是二叉树而不是 BST。

我知道我给出了一个元组，但我总是可以创建一个辅助函数来修复它，我只是认为跟踪节点会更容易。

Answer 1

如果函数不需要是 BTNode 的方法，您可以大大简化实现。然后您可以跟踪深度和总和，迭代过去 叶子并返回当前深度和总和。此外，如果您返回 (depth, sum) 元组，您可以使用 max 将它们直接相互比较:

class BTNode(object):
    def __init__(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right

def deepest_sum(node, depth=0, current=0):
    # Base case
    if not node:
        return (depth, current)

    depth += 1
    current += node.data

    return max(deepest_sum(node.left, depth, current), 
               deepest_sum(node.right, depth, current))

tree = BTNode(8, BTNode(7, BTNode(10), BTNode(11)), BTNode(6, BTNode(11), BTNode(9, None, BTNode(14))))
print(deepest_sum(tree))

输出:

(4, 37)