在Python中优化二叉树的查找直径

我想知道如何最佳地找到二叉树的直径(或任何两个叶节点之间的最长路径).我有下面的基本解决方案,但第二个解决方案需要传递指针.我怎么能在Python中做这样的事情？

def find_tree_diameter(node):
    if node == None:
        return 0

    lheight = height(node.left)
    rheight = height(node.right)

    ldiameter = find_tree_diameter(node.left)
    rdiameter = find_tree_diameter(node.right)

    return max(lheight+rheight+1, ldiameter, rdiameter)

def find_tree_diameter_optimized(node, height):
    lheight, rheight, ldiameter, rdiameter = 0, 0, 0, 0

    if node == None:
#        *height = 0;
        return 0

    ldiameter = diameterOpt(root.left, &lheight)
    rdiameter = diameterOpt(root.right, &rheight)

#    *height = max(lheight, rheight) + 1;

    return max(lh + rh + 1, max(ldiameter, rdiameter));

Paul Hankin.. 10

Python支持多个返回值,因此您不需要像C或C++那样的指针参数.这是代码的翻译:

def diameter_height(node):
    if node is None:
        return 0, 0
    ld, lh = diameter_height(node.left)
    rd, rh = diameter_height(node.right)
    return max(lh + rh + 1, ld, rd), 1 + max(lh, rh)

def find_tree_diameter(node):
    d, _ = diameter_height(node)
    return d

该函数diameter_height返回树的直径和高度,并find_tree_diameter使用它来计算直径(通过丢弃高度).

无论树的形状如何,函数都是O(n).由于重复的高度计算,当树非常不平衡时,最坏的情况下原始函数是O(n ^ 2).

Python支持多个返回值,因此您不需要像C或C++那样的指针参数.这是代码的翻译:

def diameter_height(node):
    if node is None:
        return 0, 0
    ld, lh = diameter_height(node.left)
    rd, rh = diameter_height(node.right)
    return max(lh + rh + 1, ld, rd), 1 + max(lh, rh)

def find_tree_diameter(node):
    d, _ = diameter_height(node)
    return d

该函数diameter_height返回树的直径和高度,并find_tree_diameter使用它来计算直径(通过丢弃高度).

无论树的形状如何,函数都是O(n).由于重复的高度计算,当树非常不平衡时,最坏的情况下原始函数是O(n ^ 2).