algorithm - 计算树中根左侧的节点数的函数

Question

如何计算根节点左侧的节点？这与计算树中的所有左节点不同。

标签： algorithm

Answer 1

您应该通过跟踪根与所有其他节点之间的水平距离来计算根左侧的节点。按顺序遍历树并记住当前位置（如果您向左移动，则 +1，如果向右移动，则 -1）应该足以完成这项工作。

def count_left(tree, current_position):
    if tree is None:
        return 0

    is_left = 1 if current_position > 0 else 0
    return is_left + count_left(tree.right, current_position -1) + count_left(tree.left, current_position +1)

count_left(tree.left, 1)