0543. 二叉树的直径

0543. 二叉树的直径 #

  • 标签:二叉树
  • 难度:简单

题目大意 #

给一个二叉树,计算它的直径长度。

直径长度:任意两个节点路径长度中的最大值。

例如:

1
2
3
4
5
          1
         / \
        2   3
       / \     
      4   5    

返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。

解题思路 #

这道题的重点是理解直径长度的定义。这里的直径并不是简单的「左子树高度+右子树高度」。

而是当前节点的直径 = max{左子树高度+右子树高度,所有子树中最大直径}。

也就是说当前节点的直径可能来自于 「左子树高度+右子树高度」,也可能来自于「子树中的最大直径」。

这就需要在递归求解子树高度的时候维护一个 maxDiameter 参数。每次递归都要去判断 当前「左子树高度+右子树的高度」是否大于 self.maxDiameter,然后更新最大值。

代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
    def __init__(self):
        # 保存当前最大直径
        self.maxDiameter = 0

    def diameterOfBinaryTree(self, root: TreeNode) -> int:
        self.height(root)
        return self.maxDiameter

    def height(self, root):
        if root == None:
            return 0
        leftHeight = self.height(root.left)
        rightHeight = self.height(root.right)
        self.maxDiameter = max(self.maxDiameter, leftHeight + rightHeight)

        return max(leftHeight, rightHeight) + 1
本站总访问量  次  |  您是本站第  位访问者