确定最小叶深度和该深度中叶数的算法

Question

我需要制作我在标题中指出的算法，但我有一个问题，就是我不知道如何让它写出叶子的数量

我的代码：

class Node:
    def __init__(self , key):
        self.data = key
        self.left = None
        self.right = None
 
def minDepth(root):
    if root is None:
        return 0
    if root.left is None and root.right is None:
        return 1
    if root.left is None:
        return minDepth(root.right)+1
    if root.right is None:
        return minDepth(root.left) +1
     
    return min(minDepth(root.left), minDepth(root.right))+1
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
print (minDepth(root))

所以想问一下有没有人知道怎么求某个深度的叶子数

Answer 1

在使用您当前的 DFS 算法找到最小深度后，您可以执行另一个 DFS 搜索，除非您将 'desired depth' 和 'current depth' 作为参数传递。

def count_leaves_at_depth(root, desired_depth, current_depth):
    if root is None or current_depth > desired_depth:
        return 0
    
    if root.left is None and root.right is None:
        return 1 if current_depth == desired_depth else 0
    
    if root.left is None:
        return count_leaves_at_depth(root=root.right,
                                     desired_depth=desired_depth,
                                     current_depth=current_depth + 1)
    
    if root.right is None:
        return count_leaves_at_depth(root=root.left,
                                     desired_depth=desired_depth,
                                     current_depth=current_depth + 1)

    return (count_leaves_at_depth(root=root.right,
                                  desired_depth=desired_depth,
                                  current_depth=current_depth + 1)
            + count_leaves_at_depth(root=root.left,
                                    desired_depth=desired_depth,
                                    current_depth=current_depth + 1))

print(count_leaves_at_depth(root=root,
                            desired_depth=minDepth(root),
                            current_depth=1))

确定最小叶深度和该深度中叶数的算法

An algorithm that determines the minimum leaf depth and the number of leaves in that depth

python

algorithm

binary-tree

python-3.x