题目

给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。

示例 :
给定二叉树
1
/ \
2 3
/ \
4 5
返回 3, 它的长度是路径 [4, 2, 1, 3] 或者 [5, 2, 1, 3]。

注意：两结点之间的路径长度是以它们之间边的数目表示。

方案一

  1. # Definition for a binary tree node.
  2. # class TreeNode:
  3. #     def __init__(self, x):
  4. #         self.val = x
  5. #         self.left = None
  6. #         self.right = None
  8. class Solution:
  9.     def diameterOfBinaryTree(self, root):
  10.         self.ans = 1
  11.         def depth(node):
  12.             # 访问到空节点了，返回0
  13.             if not node: return 0
  14.             # 左儿子为根的子树的深度
  15.             L = depth(node.left)
  16.             # 右儿子为根的子树的深度
  17.             R = depth(node.right)
  18.             # 计算d_node即L+R+1 并更新ans
  19.             self.ans = max(self.ans, L+R+1)
  20.             # 返回该节点为根的子树的深度
  21.             return max(L, R) + 1
  23.         depth(root)
  24.         return self.ans - 1

参考链接

https://leetcode-cn.com/explore/featured/card/2020-top-interview-questions/285/tree/1278/