解题思路
一条路径的长度为该路径经过的节点数减一，所以求直径（即求路径长度的最大值）等效于求路径经过节点数的最大值减一。而任意一条路径均可以被看作由某个节点为起点，从其左子树和右子树向下遍历的路径拼接得到。假设我们知道对于该节点的左子树向下遍历经过最多的节点数 L （即左子树的深度） 和其右子树向下遍历经过最多的节点数 R （即右子树的深度），那么以该节点为起点的路径经过节点数的最大值即为 L+R+1 。记节点 node 为起点的路径经过节点数的最大值为d_node，那么二叉树的直径就是所有节点d_node的最大值减一。
这可以通过递归算法来实现，首先定义一个递归函数depth(node)，返回该节点为根的子树的深度，先递归调用左子树，得到左子树深度为L，再递归调用右子树，得到右子树深度为R，则该节点为根的子树的深度为 max(L, R) + 1。该节点的d_note值为 L + R + 1。
递归搜索每个节点，并设置一个全局变量记录d_note的最大值，最后用 d_note - 1 就是最终结果。
步骤：
1)首先创建一个全局变量ans，用来记录d_note，并设初值为1；
2)定义递归函数：
2.1)递归结束条件为访问到空节点，返回0；
2.2)递归访问左子树，得到左子树深度 L；
2.3)递归访问右子树，得到右子树深度 R；
2.4)计算该节点为起点的路径经过节点数的最大值，即 L+R+1，并更新全局变量ans；
2.5)返回该节点为根的子树的深度，即 max(L, R) + 1；
3)对根节点进行递归，返回 ans - 1。
复杂度分析：
时间复杂度：O(N)，其中 N 为二叉树的节点数，即遍历一棵二叉树的时间复杂度，每个结点只被访问一次。
空间复杂度：O(Height)，其中 Height 为二叉树的高度。由于递归函数在递归过程中需要为每一层递归函数分配栈空间，所以这里需要额外的空间且该空间取决于递归的深度，而递归的深度显然为二叉树的高度，并且每次递归调用的函数里又只用了常数个变量，所以所需空间复杂度为 O(Height) 。
代码
# 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.ans = 1
def depth(node):
# 访问到空节点了，返回0
if not node: return 0
# 左儿子为根的子树的深度
L = depth(node.left)
# 右儿子为根的子树的深度
R = depth(node.right)
# 计算d_node即L+R+1 并更新ans
self.ans = max(self.ans, L+R+1)
# 返回该节点为根的子树的深度
return max(L, R) + 1
depth(root)
return self.ans - 1
