在Python中優化查找二叉樹的直徑

Question

我想知道如何最優地找到二叉樹的直徑（或任何兩個葉節點之間的最長路徑）。我有下面的基本解決方案，但第二個解決方案需要通過指針。我如何在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)); 

Answer 1

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）。