The diameter of a tree (sometimes called the width) is the number of nodes on the longest path between two end nodes. 

Given a binary tree, find out the diameter of it.

Sample Input:

root = [1, 2, 3, None, 4, 5, 6, None, None, None, None, 7, 8]

Sample Output:

6

For the above samle binary tree, the diameter is from node 4 to 7/8: [ 4, 2, 1, 3, 5, 7 ]. There are 6 nodes in the diameter path.

数据结构和算法：初级练习题 #41 – 二叉树直径

树的直径（有时也称作宽度），指的是树中的两个叶子节点之间最长路径的节点的数目，上面的图显示了两个树的直径都是9，形成最长路径的两个端点的叶子节点被标注了黄色（注意每个树中长度为9的路径不止一个，但是没有比9再更长的路径了）。

给定一颗树，计算它的直径。

输入样例：

root = [1, 2, 3, None, 4, 5, 6, None, None, None, None, 7, 8]

输出样例：

6

在上面这个输入样例中，树的直径是从结点4到7或8：[ 4, 2, 1, 3, 5, 7 ]，所以它的直径是6。

Python Solution