优化Python中二叉树的求直径 [英] Optimize finding diameter of binary tree in Python

问题描述

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

I'm wondering how I can optimally find the diameter (or longest path between any two leaf nodes) of a binary tree. I have the basic solution below, but the second solution requires passing pointers. How can I do something like this in 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));

推荐答案

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

Python supports multiple return values, so you don't need pointer arguments like in C or C++. Here's a translation of the code:

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 使用它来计算直径(通过丢弃高度).

The function diameter_height returns the diameter and the height of the tree, and find_tree_diameter uses it to just compute the diameter (by discarding the height).

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

The function is O(n), no matter the shape of the tree. The original function is O(n^2) in the worst case when the tree is very unbalanced because of the repeated height calculations.

这篇关于优化Python中二叉树的求直径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！