题目描述

给你一棵二叉树的根节点，返回该树的 直径 。

二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。

两节点之间路径的 长度 由它们之间边数表示。

示例 1：

输入：root = [1,2,3,4,5]
输出：3
解释：3 ，取路径 [4,2,1,3] 或 [5,2,1,3] 的长度。

示例 2：

输入：root = [1,2]
输出：1

思路

如果做过leetcode-104. 二叉树的最大深度-CSDN博客这道题，很容易可以做出本题

无非在求最大深度的代码中，加入了一个求直径的过程。直径等于左子树深度+右子树深度+1，每次和预先设置好的最大值进行比对

PS：最后返回的是self.res-1，因为我们记录的一直都是节点的个数，直径等于节点个数-1，求边的个数

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):def __init__(self):self.res = 0def depth(self, root):if not root:return 0 ldepth = self.depth(root.left)rdepth = self.depth(root.right)self.res = max(ldepth+rdepth+1, self.res)return max(ldepth,rdepth)+1def diameterOfBinaryTree(self, root):""":type root: TreeNode:rtype: int"""if not root:return 0self.depth(root)return self.res-1