二叉树的直径
题目来源：https://leetcode-cn.com/problems/diameter-of-binary-tree/
题目
给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过根结点。
示例 :
给定二叉树
1
/ \
2 3
/ \
4 5
返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
注意：两结点之间的路径长度是以它们之间边的数目表示。
解题思路
这里需要注意，二叉树的直径（最长路径），有可能不经过根节点。如下图所示：
not_through_root
在这里，求二叉树的直径，即是求最长路径。先判断问题是否划分为子问题。其实二叉树路径的问题，就是选择问题：
1
/ \
2 3
1. [左] 2 - 1
2. [右] 3 - 1
3. [左中右]，2 - 1 - 3
根据上面的解析，那么现在将问题划分为：
二叉树最长路径 = max{[左]，[右]，[左中右]}
其中 [左]，[右]，这两种情况可以用递归进行求解，因为叶子节点路径为 0，往上走，例如 2 - 1，长度 + 1，也就是左右节点递归返回值 + 1。
而 [左中右] 这种情况情况，其实就是 左 + 右。
代码实现
class Solution:
def diameterOfBinaryTree(self, root: TreeNode) -> int:
self.ans = 0
def diameter_of_binary_tree(node, ans):
# 递归出口
if not node:
return 0
# 递归获取左右两种情况的直径
left_depth = diameter_of_binary_tree(node.left, self.ans)
right_depth = diameter_of_binary_tree(node.right, self.ans)
# 左中右的情况
self.ans = max(self.ans, left_depth + right_depth)
# 递归获取的结果
return max(left_depth, right_depth) + 1
diameter_of_binary_tree(root, self.ans)
return self.ans
实现结果
二叉树的直径--实现结果
以上就是使用递归的方法，解决《二叉树的直径》问题的主要内容。
欢迎关注微信公众号《书所集录》
