二叉树的直径 - 更好的设计

Question

二叉树的直径 - 更好的设计

16

我写了一段代码用于查找二叉树的直径。需要以下建议：

我是否可以不使用类级别的静态变量来实现这个功能？
这个算法是否可行/有什么建议？

public class DiameterOfTree {   
public static int diameter = 0; 
public static int getDiameter(BinaryTreeNode root) {        
    if (root != null) {                     
        int leftCount = getDiameter(root.getLeft());
        int rightCount = getDiameter(root.getRight());
        if (leftCount + rightCount > diameter) {
            diameter = leftCount + rightCount;
            System.out.println("---diameter------------->" + diameter);
        }           
        if ( leftCount > rightCount) {
            return leftCount + 1;
        }
        return rightCount + 1;
    }
    return 0;
  }
}

- Manish

1

“is the algorithm fine?”的意思是算法可行吗？你测试过代码了吗？ - arunmoezhi

Arun，当然我已经测试过代码了。我的意思是说，是否有更好的算法？ - Manish

3

这个问题也可以在[CodeReview.SE]上得到很好的解答。 - S.L. Barth

@Barth，谢谢。我不知道有代码审查这个功能。我也会去试试看。 - Manish

@Manish 哦，好的。请参考这个链接：http://www.geeksforgeeks.org/archives/5687 - arunmoezhi

除了面试之外，找到二叉树的直径还有其他用途吗？ - Jeff

11个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- vijay9908 · Answer 1

最有效的方法是计算直径和高度以达到O(n)，以下是实现此目标的最简单方法[Python3，PyPy3]

for this definition for a binary tree node,
class TreeNode:
     def __init__(self, x):
         self.val = x
         self.left = None
         self.right = None

class Solution:
def diameterOfBinaryTree(self, root: TreeNode) -> int:
    self.height = 1

    def height(node):
        if node is None:
            return 0
        l_height = height(node.left)
        r_height = height(node.right)
        self.height = max(self.height,l_height+r_height+1)
        return max(l_height,r_height) + 1

    height(root)
    return self.height-1

最简单、最实惠的解决方案，运行时间更快，复杂度更低。